NC20279 [SCOI2010]序列操作

题目

题目描述

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

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

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

输入描述

第二行包括n个数，表示序列的初始状态
接下来m行，每行3个数，op, a, b，（0 ≤ op ≤ 4，0 ≤ a ≤ b）

输出描述

示例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

输出

备注

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

题解

知识点：线段树。

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

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

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

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

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

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

空间复杂度 \(O(n\

代码

#include <bits/stdc++.h>
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 T, class F>
class SegmentTreeLazy {
    int n;
    vector<T> node;
    vector<F> 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<T> &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<T> &src {
        init(_n;
        function<void(int, int, int> 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<T> 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<T, F> 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;
}

编程笔记 » NC20279 [SCOI2010]序列操作

NC20279 [SCOI2010]序列操作

题目

题解

代码

相关文章

Hi，您需要填写昵称和邮箱！