BZOJ4355 Play with sequence < SegBeats >

Problem

Play with sequence

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

维护一个长度为$N$的序列$a$，现在有三种操作：

1. 给出参数$U,V,C$，将$a[U],a[U+1],...,a[V-1],a[V]$都赋值为$C$。
2. 给出参数$U,V,C$，对于区间$[U,V]$里的每个数$i$，将$a[i]$赋值为$\max(a[i]+C,0)$。
3. 给出参数$U,V$，输出$a[U],a[U+1],...,a[V-1],a[V]$里值为$0$的数字个数。

Input

第一行包含两个正整数$N,M\;(1\le N,M\le3\times10^5)$，分别表示序列长度和操作个数。
第二行包含$N$个整数，其中第$i$个数表示$a[i]\;(0\le a[i]\le10^9)$，描述序列的初始状态。
接下来$M$行描述$M$个操作，保证$1\le U\le V\le N$，对于操作$1$，$0\le C\le10^9$，对于操作$2$，$|C|\le10^9$。

Output

输出若干行，每行一个整数，依次回答每个操作$3$的问题。

Sample Input

5 3
6 4 6 6 4 
2 1 5 -5
1 3 4 4
3 1 5

Sample Output

2

Source

2016.1.1新加数据
鸣谢Claris

标签：SegBeats 线段树

Solution

$\mathrm{Segment\;Tree\;Beats!}$
参见吉老师的冬令营课件。

令二元组$(x,c)$表示对于区间$[l,r]$中的每个数先$+x$再$\%c$，发现这样的二元组是可以合并的。
对于二元组$(x_1,c_1)$和$(x_2,c_2)$，前者在后者的前面出现，则合并起来变成$(x_1+x_2,\min(c_1+x_2,c_2))$。
维护每个区间的最小值、次小值、最小值个数即可。若某区间$\mathrm{downtag}$后最小值和次小值的大小关系未发生改变，那么不需要递归到子区间重新打擂。$\mathrm{SegBeats}$维护即可。

Code

#include <bits/stdc++.h>
#define MAX_N 300000
#define INF (1LL<<50)
#define mid ((s+t)>>1)
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m;
struct Tag {lnt x, c;} tag[MAX_N<<2];
struct Node {lnt mi1, mi2; int cnt, tot;} tr[MAX_N<<2];
Node operator + (Node a, Node b) {
    Node ret = (Node){0, 0, 0, a.tot+b.tot};
    if (a.mi1 == b.mi1) ret.mi1 = a.mi1, ret.cnt = a.cnt+b.cnt, ret.mi2 = min(a.mi2, b.mi2);
    else if (a.mi1 < b.mi1) ret.mi1 = a.mi1, ret.cnt = a.cnt, ret.mi2 = min(a.mi2, b.mi1);
    else ret.mi1 = b.mi1, ret.cnt = b.cnt, ret.mi2 = min(a.mi1, b.mi2); return ret;
}
Tag operator + (Tag a, Tag b) {return (Tag){max(a.x+b.x, -INF), max(a.c+b.x, b.c)};}
void build(int v, int s, int t) {
    tag[v] = (Tag){0, -INF};
    if (s == t) {read(tr[v].mi1), tr[v].mi2 = INF, tr[v].cnt = 1, tr[v].tot = 0; return;}
    build(v<<1, s, mid), build(v<<1|1, mid+1, t), tr[v] = tr[v<<1]+tr[v<<1|1];
}
void maintain(int v, Tag tg) ;
void downtag(int v) {
    tag[v<<1] = tag[v<<1]+tag[v], tag[v<<1|1] = tag[v<<1|1]+tag[v];
    maintain(v<<1, tag[v]), maintain(v<<1|1, tag[v]), tag[v] = (Tag){0, -INF};
}
void maintain(int v, Tag tg) {
    lnt tmi1 = max(max(tr[v].mi1+tg.x, tg.c), 0LL);
    lnt tmi2 = max(max(tr[v].mi2+tg.x, tg.c), 0LL);
    tmi1 = min(tmi1, INF), tmi2 = min(tmi2, INF);
    if (tr[v].mi2 == INF) tmi2 = INF;
    if (tmi1 < tmi2)
        tr[v].mi1 = tmi1, tr[v].mi2 = tmi2, 
        tr[v].tot = tmi1 ? 0 : tr[v].cnt;
    else downtag(v), tr[v] = tr[v<<1]+tr[v<<1|1];
}
void modify(int v, int s, int t, int l, int r, Tag tg) {
    if (s >= l && t <= r) {tag[v] = tag[v]+tg, maintain(v, tg); return;}
    downtag(v);
    if (l <= mid) modify(v<<1, s, mid, l, r, tg);
    if (r >= mid+1) modify(v<<1|1, mid+1, t, l, r, tg);
    tr[v] = tr[v<<1]+tr[v<<1|1];
}
int query(int v, int s, int t, int l, int r) {
    if (s >= l && t <= r) return tr[v].tot;
    int ret = 0; downtag(v);
    if (l <= mid) ret += query(v<<1, s, mid, l, r);
    if (r >= mid+1) ret += query(v<<1|1, mid+1, t, l, r);
    tr[v] = tr[v<<1]+tr[v<<1|1]; return ret;
}
int main() {
    read(n), read(m), build(1, 1, n);
    while (m--) {
        int opt, l, r, x; read(opt), read(l), read(r);
        if (opt == 1) read(x), modify(1, 1, n, l, r, (Tag){-INF, x});
        if (opt == 2) read(x), modify(1, 1, n, l, r, (Tag){x, 0});
        if (opt == 3) printf("%d\n", query(1, 1, n, l, r));
    }
    return 0;
}