全球速读：NC20279 [SCOI2010]序列操作

题目链接

(资料图)

题目描述

lxhgww最近收到了一个01序列，序列里面包含了n个数，这些数要么是0，要么是1，现在对于这个序列有五种变换操作和询问操作：

0 a b 把[a, b]区间内的所有数全变成0

1 a b 把[a, b]区间内的所有数全变成1

2 a b 把[a,b]区间内的所有数全部取反，也就是说把所有的0变成1，把所有的1变成0

3 a b 询问[a, b]区间内总共有多少个1

4 a b 询问[a, b]区间内最多有多少个连续的1

对于每一种询问操作，lxhgww都需要给出回答，聪明的程序员们，你们能帮助他吗？

输入描述

输入数据第一行包括2个数，n和m，分别表示序列的长度和操作数目第二行包括n个数，表示序列的初始状态接下来m行，每行3个数，op, a, b，（0 ≤ op ≤ 4，0 ≤ a ≤ b）

输出描述

对于每一个询问操作，输出一行，包括1个数，表示其对应的答案

示例1

输入

10 100 0 0 1 1 0 1 0 1 11 0 23 0 52 2 24 0 40 3 62 3 74 2 81 0 50 5 63 3 9

输出

5265

备注

对于30%的数据， \(1\le n,m \le 1000\) ；对于100%的数据， \(1\le n,m \le 10^5\) 。

知识点：线段树。

这一道题维护的信息较多需要逐一分析。

为了方便求区间长度，还有取反的操作，我们将 \(0,1\) 的信息都维护一下，但接下来只讲 \(1\) 的部分， \(0\) 同 \(1\) 就不讲了。

首先需要维护的是 \(1\) 的数量 \(sum1\) ，以及连续 \(1\) 个数的最大值 \(max1\) 。

在合并时， \(sum1\) 直接加即可。 \(max1\) 不仅要取子区间的 \(max1\) ， 还需要考虑左子区间从右端点开始连续的 \(1\) ，以及右子区间从左端点开始连续的 \(1\) ，两部分拼起来的长度。因此还需要维护，区间从左端点开始连续 \(1\) 的个数 \(left1\) ，从右端点开始连续 \(1\) 的个数 \(right1\) 。

对于 \(left1,right1\) ，在合并时，要考虑一个特殊情况，左子区间 \(left1\) 等于区间长度（可用 \(sum0 + sum1\) 表示），那么他可以与右子区间的 \(left1\) 相加，得到区间的 \(left1\) ， \(right1\) 同理。除此之外，直接继承即可。

因此，区间信息需要维护 \(sum0/1,max0/1,left0/1,right0/1\) 。

区间修改需要维护三种修改标记：全 \(0\) 、全 \(1\) 、取反。三种的区间修改都十分好实现，前两种直接改为区间长度，取反交换 \(0/1\) 即可。另外，考虑到标记下传需要一个标记表示没有修改，即单位元值，以供函数特判。

因此，区间修改需要维护 \(0/1/2/3\) （无修改、全 \(0\) 、全 \(1\) 、取反）。

懒标记的修改需要分类讨论：

于是所有信息就维护完了。

时间复杂度 \(O((n+m) \log n)\)

空间复杂度 \(O(n)\)

#include using namespace std;using ll = long long;struct T {    int sum0, sum1;    int max0, max1;    int left0, left1;    int right0, right1;    static T e() {        return {            0,0,            0,0,            0,0,            0,0        };    }    friend T operator+(const T &a, const T &b) {        return{            a.sum0 + b.sum0,a.sum1 + b.sum1,            max({a.max0,b.max0,a.right0 + b.left0}),max({a.max1,b.max1,a.right1 + b.left1}),            a.left0 == a.sum0 + a.sum1 ? a.left0 + b.left0 : a.left0,a.left1 == a.sum0 + a.sum1 ? a.left1 + b.left1 : a.left1,            b.right0 == b.sum0 + b.sum1 ? b.right0 + a.right0 : b.right0,b.right1 == b.sum0 + b.sum1 ? b.right1 + a.right1 : b.right1        };    }};struct F {    int op;    static F e() { return{ 0 }; }    T operator()(const T &x) {        if (op == 0) return x;        else if (op == 1) return {            x.sum0 + x.sum1,0,            x.sum0 + x.sum1,0,            x.sum0 + x.sum1,0,            x.sum0 + x.sum1,0        };        else if (op == 2) return{            0,x.sum0 + x.sum1,            0,x.sum0 + x.sum1,            0,x.sum0 + x.sum1,            0,x.sum0 + x.sum1        };        else return{            x.sum1,x.sum0,            x.max1,x.max0,            x.left1,x.left0,            x.right1,x.right0        };    }    F operator() (const F &g) {        if (op == 0) return g;        else if (op == 1) return { 1 };        else if (op == 2) return { 2 };        else {            if (g.op == 0) return { 3 };            else if (g.op == 1) return { 2 };            else if (g.op == 2) return { 1 };            else return { 0 };        }    }};templateclass SegmentTreeLazy {    int n;    vector node;    vector lazy;    void push_down(int rt) {        node[rt << 1] = lazy[rt](node[rt << 1]);        lazy[rt << 1] = lazy[rt](lazy[rt << 1]);        node[rt << 1 | 1] = lazy[rt](node[rt << 1 | 1]);        lazy[rt << 1 | 1] = lazy[rt](lazy[rt << 1 | 1]);        lazy[rt] = F::e();    }    void update(int rt, int l, int r, int x, int y, F f) {        if (r < x || y < l) return;        if (x <= l && r <= y) return node[rt] = f(node[rt]), lazy[rt] = f(lazy[rt]), void();        push_down(rt);        int mid = l + r >> 1;        update(rt << 1, l, mid, x, y, f);        update(rt << 1 | 1, mid + 1, r, x, y, f);        node[rt] = node[rt << 1] + node[rt << 1 | 1];    }    T query(int rt, int l, int r, int x, int y) {        if (r < x || y < l) return T::e();        if (x <= l && r <= y) return node[rt];        push_down(rt);        int mid = l + r >> 1;        return query(rt << 1, l, mid, x, y) + query(rt << 1 | 1, mid + 1, r, x, y);    }public:    SegmentTreeLazy(int _n = 0) { init(_n); }    SegmentTreeLazy(int _n, const vector &src) { init(_n, src); }    void init(int _n) {        n = _n;        node.assign(n << 2, T::e());        lazy.assign(n << 2, F::e());    }    void init(int _n, const vector &src) {        init(_n);        function build = [&](int rt, int l, int r) {            if (l == r) return node[rt] = src[l], void();            int mid = l + r >> 1;            build(rt << 1, l, mid);            build(rt << 1 | 1, mid + 1, r);            node[rt] = node[rt << 1] + node[rt << 1 | 1];        };        build(1, 1, n);    }    void update(int x, int y, const F &f) { update(1, 1, n, x, y, f); }    T query(int x, int y) { return query(1, 1, n, x, y); }};int main() {    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);    int n, m;    cin >> n >> m;    vector a(n + 1);    for (int i = 1;i <= n;i++) {        int x;        cin >> x;        a[i] = { 1 - x,x,1 - x,x,1 - x,x,1 - x,x };    }    SegmentTreeLazy sgt(n, a);    while (m--) {        int op, l, r;        cin >> op >> l >> r;        l++, r++;        if (op == 0) sgt.update(l, r, { 1 });        else if (op == 1) sgt.update(l, r, { 2 });        else if (op == 2) sgt.update(l, r, { 3 });        else if (op == 3) cout << sgt.query(l, r).sum1 << "\n";        else cout << sgt.query(l, r).max1 << "\n";    }    return 0;}