题目链接

题目

题目描述

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 10
0 0 0 1 1 0 1 0 1 1
1 0 2
3 0 5
2 2 2
4 0 4
0 3 6
2 3 7
4 2 8
1 0 5
0 5 6
3 3 9

输出

5
2
6
5

备注

对于30%的数据， (1le n,m le 1000) ；
对于100%的数据， (1le 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) 、取反）。

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

1. 修改为未修改，则新标记维持原状。
2. 修改为全 (0) ，则新标记为全 (0) 。
3. 修改为全 (1) ，则新标记为全 (1) 。
4. 修改为取反，则分类讨论：
   1. 若原标记为未修改，则新标记为取反。
   2. 若原标记为全 (0) ，则新标记为全 (1) 。
   3. 若原标记为全 (1) ，则新标记为全 (0) 。
   4. 若原标记为取反，则新标记为未修改。

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

时间复杂度 (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 };
        }
    }
};

template
class SegmentTreeLazy {
    int n;
    vector node;
    vector lazy;

    void push_down(int rt) {
        node[rt > 1;
        update(rt > 1;
        return query(rt  &src) { init(_n, src); }
    void init(int _n) {
        n = _n;
        node.assign(n  &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 > n >> m;
    vector a(n + 1);
    for (int i = 1;i > 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 

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.e1idc.net