\(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\)。

二、线段树解法

懒标记传递流程

• \(modify()\)
  ① 若整体命中，调用\(change()\)处理当前区间
  ② 未整体命中，\(pushdown()\),然后分裂
  ③ 视为套路性代码

• \(change()\)
  ① 根据懒标记,修改当前区间统计信息
  ② 整理当前区间懒标记,以便向下推送

• \(pushdown()\)
  ① 如果存在某个懒标记，调用\(change()\)处理左右儿子区间，清空懒标记
  ② 视为套路性代码

#include <bits/stdc++.h>
using namespace std;
const int N = 200010;

// 线段树，求区间连续序列长度
#define mid ((l + r) >> 1)
#define ls (u << 1)
#define rs (u << 1 | 1)
struct Node {
    int l, r, len;
    int sum;                 // 区间中数字1个数
    int mx[2], lx[2], rx[2]; // 区间内连续最长数字1，左起最长数字1长度，右起最长数字1长度
    int turn, assign;        // 取反懒标记，赋值懒标记

} tr[N << 2];

void pushup(int u) {
    // 更新需要更新的属性，本题是1+2+2+2=7个需要更新的属性
    tr[u].sum = tr[ls].sum + tr[rs].sum; // 区间中1的个数为左右子树中1的个数和

    for (int i = 0; i <= 1; i++) {
        tr[u].lx[i] = tr[ls].lx[i];                                    // 继承左儿子的左端点最多连续0/1个数
        if (tr[ls].sum == i * tr[ls].len) tr[u].lx[i] += tr[rs].lx[i]; // 如果左儿子全是0/1，那么加上右儿子的左端点最长连续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];

        tr[u].mx[i] = max({tr[ls].mx[i], tr[rs].mx[i], tr[ls].rx[i] + tr[rs].lx[i]});
    }
}

void build(int u, int l, int r) {
    tr[u].l = l, tr[u].r = r, tr[u].len = r - l + 1;
    tr[u].assign = -1;
    if (l == r) {
        int v;
        cin >> v;
        tr[u].sum = v;
        tr[u].mx[v] = tr[u].lx[v] = tr[u].rx[v] = 1;
        return;
    }
    build(ls, l, mid), build(rs, mid + 1, r);
    pushup(u);
}

void change_turn(int u) {
    // 处理统计信息
    tr[u].sum = tr[u].len - tr[u].sum;
    swap(tr[u].mx[1], tr[u].mx[0]);
    swap(tr[u].lx[1], tr[u].lx[0]);
    swap(tr[u].rx[1], tr[u].rx[0]);
    // 处理懒标记
    if (tr[u].assign != -1)
        tr[u].assign ^= 1;
    else
        tr[u].turn ^= 1;
}

void change_all(int u, int v) {
    // 处理统计信息
    tr[u].mx[1] = tr[u].lx[1] = tr[u].rx[1] = tr[u].sum = v * tr[u].len;
    tr[u].mx[0] = tr[u].lx[0] = tr[u].rx[0] = tr[u].len - tr[u].sum;
    // 处理懒标记
    tr[u].assign = v;
    tr[u].turn = 0;
}


void pushdown(int u) { // 下传懒标记
    // 多个懒标记的处理原则：谁的优先级高就先处理谁,很明显，本题中的赋值运算优先级高
    if (tr[u].assign != -1) {         // 如果存在赋值懒标记
        change_all(ls, tr[u].assign); // 向左儿子传递懒标记
        change_all(rs, tr[u].assign); // 向右儿子传递懒标记
        tr[u].assign = -1;            // 清空赋值懒标记
    }
    if (tr[u].turn) {    // 如果存在取反的懒标记
        change_turn(ls); // 向左儿子传递懒标记
        change_turn(rs); // 向右儿子传递懒标记
        tr[u].turn = 0;  // 清空取反懒标记
    }
}

void modify_turn(int u, int L, int R) {
    int l = tr[u].l, r = tr[u].r;
    if (l >= L && r <= R) {
        change_turn(u);
        return;
    }
    if (l > R || r < L) return;

    pushdown(u);
    modify_turn(ls, L, R), modify_turn(rs, L, R);
    pushup(u);
}

void modify_assign(int u, int L, int R, int v) {
    int l = tr[u].l, r = tr[u].r;
    if (l >= L && r <= R) {
        change_all(u, v);
        return;
    }
    if (l > R || r < L) return;

    pushdown(u);
    modify_assign(ls, L, R, v), modify_assign(rs, L, R, v);
    pushup(u);
}

int query_all(int u, int L, int R) {
    int l = tr[u].l, r = tr[u].r;
    if (l >= L && r <= R) return tr[u].sum;
    if (l > R || r < L) return 0;

    pushdown(u);
    return query_all(ls, L, R) + query_all(rs, L, R);
}

int query_continue(int u, int L, int R) {
    int l = tr[u].l, r = tr[u].r;
    if (L <= l && r <= R) return tr[u].mx[1];
    if (r < L || l > R) return 0;

    pushdown(u);
    return max({query_continue(ls, L, R), query_continue(rs, L, R), 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);
    int n, m;
    cin >> n >> m;
    build(1, 0, n - 1);
    while (m--) {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 0) modify_assign(1, l, r, 0);
        if (op == 1) modify_assign(1, l, r, 1);
        if (op == 2) modify_turn(1, l, r);
        if (op == 3) printf("%d\n", query_all(1, l, r));      // 区间内总共有多少个1
        if (op == 4) printf("%d\n", query_continue(1, l, r)); // 区间内最多有多少个连续的1
    }
    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;
}