526互联

SCOI2010 P2572 序列操作

发布时间 2023-09-04 19:26:23作者: 糖豆爸爸

\(SCOI2010\) \(P2572\) 序列操作

一、题目描述

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

  • 0 l r 把 \([l, r]\) 区间内的所有数全变成 \(0\)

  • 1 l r 把 \([l, r]\) 区间内的所有数全变成 \(1\)

  • 2 l r 把 \([l,r]\) 区间内的所有数全部取反，也就是说把所有的 \(0\) 变成 \(1\)，把所有的 \(1\) 变成 \(0\)

  • 3 l r 询问 \([l, r]\) 区间内总共有多少个 \(1\)

  • 4 l r 询问 \([l, r]\) 区间内最多有多少个连续的 \(1\)

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

输入格式

第一行两个正整数 \(n,m\)，表示序列长度与操作个数。
第二行包括 \(n\) 个数，表示序列的初始状态。
接下来 \(m\) 行，每行三个整数，表示一次操作。

输出格式

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

样例输入 #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

样例输出 #1

5
2
6
5

提示

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

二、线段树解法

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 50;

#define mid ((l + r) >> 1)
#define ls u << 1
#define rs u << 1 | 1
struct Node {
    int l, r;
    int len;   // 区间长度
    int fz;    // 懒标记：区间是否整个被赋值
    int qf;    // 懒标记：区间是否被反转
    int sum;   // 区间1的个数
    int mx[2]; // 区间最多的连续0/1个数
    int lx[2]; // 区间从左端点开始最多的连续的0/1个数
    int rx[2]; // 区间从右端点开始最多的连续的0/1个数
} tr[N << 2];

int n, m;

void pushup(int u) {
    tr[u].sum = tr[ls].sum + tr[rs].sum; // 区间中1的个数为左右子树中1的个数和

    for (int i = 0; i < 2; i++) { // 分别讨论区间中0 1的情况
        // 区间从左端点开始最多的连续的0/1的个数
        tr[u].lx[i] = tr[ls].lx[i];
        if (tr[ls].sum == i * tr[ls].len) tr[u].lx[i] += tr[rs].lx[i];

        // 区间从右端点开始最多的连续的0/1的个数
        tr[u].rx[i] = tr[rs].rx[i];
        if (tr[rs].sum == i * tr[rs].len) tr[u].rx[i] += tr[ls].rx[i];

        // 区间最多的连续0/1个数
        /*
        ① 左儿子的区间最多的连续个数
        ② 右儿子的区间最多的连续个数
        ③ 左儿子的右最长+右儿子的左最长
        */
        tr[u].mx[i] = max({tr[ls].rx[i] + tr[rs].lx[i], tr[ls].mx[i], tr[rs].mx[i]});
    }
}

void build(int u, int l, int r) {
    tr[u].l = l, tr[u].r = r; // 管辖范围
    tr[u].fz = -1;            // 懒标记初值:是否被赋值
    tr[u].qf = -1;            // 懒标记初值:是否被覆盖
    tr[u].len = r - l + 1;    // 区间长度

    if (l == r) { // 叶子节点
        int v;
        cin >> v;
        tr[u].sum = v;   // v=1:区间内1的个数为1；v=0:区间内0的个数为0；
        tr[u].mx[v] = 1; // v=1:区间中连续为0的个数为1;v=0:区间内连续为0的个数为1；
        tr[u].lx[v] = 1; // v=1:区间从左端点开始最多的连续的1的个数为1;v=0:区间从左端点开始最多的连续的0的个数为1;
        tr[u].rx[v] = 1; // v=1:区间从右端点开始最多的连续的1的个数为1;v=0:区间从右端点开始最多的连续的0的个数为1;
        return;
    }
    build(ls, l, mid);     // 构建左子树
    build(rs, mid + 1, r); // 构建右子树
    pushup(u);             // 向上汇总统计信息
}

void pushdown(int u) {
    if (~tr[u].fz) { // 区间赋值懒标记不空
        int v = tr[u].fz;
        tr[ls].fz = tr[rs].fz = v;  // 向左右儿子传递赋值懒标记
        tr[ls].qf = tr[rs].qf = -1; // 清空左右儿子的取反懒标记

        tr[ls].sum = v * tr[ls].len; // v=1:sum=区间长度；v=0:sum=0
        tr[rs].sum = v * tr[rs].len;

        tr[ls].mx[v] = tr[ls].lx[v] = tr[ls].rx[v] = tr[ls].len;
        tr[ls].mx[v ^ 1] = tr[ls].lx[v ^ 1] = tr[ls].rx[v ^ 1] = 0;

        tr[rs].mx[v] = tr[rs].lx[v] = tr[rs].rx[v] = tr[rs].len;
        tr[rs].mx[v ^ 1] = tr[rs].lx[v ^ 1] = tr[rs].rx[v ^ 1] = 0;

        // 下传懒标记完毕
        tr[u].fz = -1;
        tr[u].qf = -1;
        return;
    }

    if (~tr[u].qf) {    // 本次是取反懒标记下传
        tr[ls].qf ^= 1; // 向左儿子传递取反懒标记
        tr[rs].qf ^= 1; // 向右儿子传递取反懒标记

        if (~tr[ls].fz) tr[ls].fz ^= 1; // 如果原来左儿子存在赋值懒标记，那么就整体赋反值吧
        if (~tr[rs].fz) tr[rs].fz ^= 1; // 如果原来右儿子存在赋值懒标记，那么就整体赋反值吧

        // 取反，需要处理左右儿子的数字1个数的统计属性
        tr[ls].sum = tr[ls].len - tr[ls].sum; // 共10个长度，原来有3个数字1，取反后，就是有3个0，7个1
        tr[rs].sum = tr[rs].len - tr[rs].sum;

        // 取反，需要处理
        swap(tr[ls].mx[0], tr[ls].mx[1]);
        swap(tr[ls].lx[0], tr[ls].lx[1]);
        swap(tr[ls].rx[0], tr[ls].rx[1]);

        swap(tr[rs].mx[0], tr[rs].mx[1]);
        swap(tr[rs].lx[0], tr[rs].lx[1]);
        swap(tr[rs].rx[0], tr[rs].rx[1]);

        // 清空取反懒标记
        tr[u].qf = -1;
    }
}

void modify(int u, int L, int R, int op) {
    int l = tr[u].l, r = tr[u].r, len = r - l + 1; // 范围
    if (r < L || l > R) return;                    // 当前区间与修改区间无交集时
    if (l >= L && r <= R) {
        if (op <= 1) {                                                  // 0: 区间内的所有数全变成 0; 1: 区间内的所有数全变成 1;
            tr[u].fz = op;                                              // 统一修改的懒标记
            tr[u].qf = 0;                                               // 既然都统一修改了，取反的懒标记就无效了，就听统一修改的了
            tr[u].sum = op * len;                                       // 如果op==1,那么就是整个区间都是1，区间长度就是区间和; 如果op==0,那么就是整个区间都是0
            tr[u].mx[op] = tr[u].lx[op] = tr[u].rx[op] = len;           // 区间连续，左起最长，右起最长都是区间长度
            tr[u].mx[op ^ 1] = tr[u].lx[op ^ 1] = tr[u].rx[op ^ 1] = 0; // 异或取反的都设置为0
            return;
        } else {                               // op==2,区间内的所有数全部取反
            tr[u].qf ^= 1;                     // 将整体区间取反，这里似乎有点问题，应该是初值是-1才对，为什么这里初始值是0
            if (tr[u].fz != -1) tr[u].fz ^= 1; // fz: 整体变0/1; 如果懒标记不是初值，那么懒标记取反,就起到了反转的作用

            tr[u].sum = len - tr[u].sum; // 区间长度为10，原来数字1个数为3，那么数字0个数为7。现在取反，则3=>7
            swap(tr[u].mx[0], tr[u].mx[1]);
            swap(tr[u].lx[0], tr[u].lx[1]);
            swap(tr[u].rx[0], tr[u].rx[1]);
            return;
        }
    }
    // 分裂前pushdown下传懒标记
    pushdown(u);
    modify(ls, L, R, op), modify(rs, L, R, op);
    pushup(u);
}

int query(int u, int L, int R, int op) {
    int l = tr[u].l, r = tr[u].r;
    if (r < L || l > R) return 0; // 当前区间与修改区间无交集时

    if (L <= l && r <= R) {
        if (op == 3) return tr[u].sum;   // 区间中数字1的个数
        if (op == 4) return tr[u].mx[1]; // 区间内最多有多少个连续的1,这是怎么汇总统计求出来的？没看懂！
    }

    pushdown(u);

    // 区间内总共有多少个 1
    if (op == 3) return query(ls, L, R, op) + query(rs, L, R, op);

    // 区间内最多有多少个连续的 1
    // 先来检查左儿子的最长连续1，再来检查右儿子的最长连续1
    // 画图理解
    if (op == 4) return max({query(ls, L, R, op), query(rs, L, R, op),
                             min(mid - L + 1, tr[ls].rx[1]) + min(R - mid, tr[rs].lx[1])});
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("P2572.in", "r", stdin);
#endif
    // 加快读入
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n >> m;

    build(1, 0, n - 1); // 构建线段树,root=1,管辖范围 [0,n-1]

    while (m--) {
        int op, l, r;
        cin >> op >> l >> r;
        if (op < 3)
            modify(1, l, r, op);
        else
            printf("%d\n", query(1, l, r, op));
    }
    return 0;
}

三、柯朵莉树解法

#include <bits/stdc++.h>

using namespace std;

// 11个测试点，只能通过3个测试点
// 柯朵莉树模板
struct Node {
    int l, r;      // l和r表示这一段的起点和终点
    mutable int v; // v表示这一段上所有元素相同的值是多少,注意关键字 mutable,使得set中结构体属性可修改
    bool operator<(const Node &b) const {
        return l < b.l; // 规定按照每段的左端点排序
    }
};
set<Node> s; // 柯朵莉树的区间集合

// 分裂:[l,x-1],[x,r]
set<Node>::iterator split(int x) {
    auto it = s.lower_bound({x});
    if (it != s.end() && it->l == x) return it; // 一击命中
    it--;                                       // 没有找到就减1个继续找
    if (it->r < x) return s.end();              // 真的没找到,返回s.end()

    int l = it->l, r = it->r, v = it->v; // 没有被返回，说明找到了,记录下来，防止后面删除时被破坏
    s.erase(it);                         // 删除整个区间
    s.insert({l, x - 1, v});             //[l,x-1]拆分
    // insert函数返回pair，其中的first是新插入结点的迭代器
    return s.insert({x, r, v}).first; //[x,r]拆分
}

// 区间加
void add(int l, int r, int v) {
    // 必须先计算itr,后计算itl
    auto R = split(r + 1), L = split(l);
    for (auto it = L; it != R; it++) it->v += v;
}
// 区间赋值
void assign(int l, int r, int v) {
    auto R = split(r + 1), L = split(l);
    s.erase(L, R);       // 删除旧区间
    s.insert({l, r, v}); // 增加新区间
}

void change(int l, int r) {
    auto R = split(r + 1), L = split(l);
    for (auto it = L; it != R; it++) it->v = !it->v; // 取反,暴力
}

int count1(int l, int r) {
    int res = 0;
    auto R = split(r + 1), L = split(l);
    for (auto it = L; it != R; it++)
        res += (it->r - it->l + 1) * it->v;
    return res;
}
// 多少个连续的1
int count2(int l, int r) {
    int res = 0;

    int t = 0;
    auto R = split(r + 1), L = split(l);
    for (auto it = L; it != R; it++)
        if (it->v) {
            t += it->r - it->l + 1;
            res = max(res, t); // 一定要在t变大后马上取max,不能在下面else里取 max,那样最后的区间会无法得到，造成错误！
        } else
            t = 0;
    return res;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("P2572.in", "r", stdin);
#endif
    // 加快读入
    ios::sync_with_stdio(false), cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        // 下标从 0 开始
        int x;
        cin >> x;
        s.insert({i, i, x}); // 初始化柯朵莉树
    }
    while (m--) {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 0) assign(l, r, 0);
        if (op == 1) assign(l, r, 1);
        if (op == 2) change(l, r);
        if (op == 3) cout << count1(l, r) << endl;
        if (op == 4) cout << count2(l, r) << endl;
    }
    return 0;
}