[SCOI2010] 序列操作

形式化题目

给定一个长度 $n$ 的 0/1 序列，支持 $m$ 次操作：

把区间 $[l, r]$ 全部赋值为 0；
把区间 $[l, r]$ 全部赋值为 1；
把区间 $[l, r]$ 全部取反（0 变 1、1 变 0）；
询问区间 $[l, r]$ 内 1 的个数；
询问区间 $[l, r]$ 内最长连续 1 的长度。

要求按顺序处理全部操作并输出每次询问的答案。

思路

先看一个可以直接验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-12 22:11
 * update_at: 2026-08-12 22:15
 */
// brute.cpp：小数据暴力解，直接逐元素模拟五种操作，用来理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;

int n, m;
int a[MAXN]; // a[i] 表示序列第 i 个位置的值（按题目下标从 0 开始）

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    for (int i = 1; i <= m; i++) {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 0 || op == 1) {
            // 区间赋值：逐元素直接赋值。
            for (int j = l; j <= r; j++)
                a[j] = op;
        } else if (op == 2) {
            // 区间翻转：逐元素取反。
            for (int j = l; j <= r; j++)
                a[j] = 1 - a[j];
        } else if (op == 3) {
            // 查询 1 的个数：逐元素统计。
            int cnt = 0;
            for (int j = l; j <= r; j++)
                if (a[j] == 1)
                    cnt++;
            cout << cnt << '\n';
        } else {
            // 查询最长连续 1：逐元素扫描并更新当前连续段长度。
            int best = 0, cur = 0;
            for (int j = l; j <= r; j++) {
                if (a[j] == 1) {
                    cur++;
                    if (best < cur) best = cur;
                } else {
                    cur = 0;
                }
            }
            cout << best << '\n';
        }
    }
    return 0;
}

brute.cpp 逐元素模拟五种操作，单次操作 $O(n)$ ，总复杂度 $O(nm)$ ，无法通过 $10^5$ 的数据。

本题比普通区间翻转题难在两点：最长连续 1 不是可加信息（要知道左端、右端各自的连续段才能合并），翻转让 0 变成 1（只统计 1 无法回答翻转后的查询）。于是节点必须同时维护 0 和 1 两套对称统计：

sum：区间内 1 的个数（0 的个数 = 长度 - sum）；
pref1 / suff1 / best1：1 的"左前缀 / 右后缀 / 最长连续段"；
pref0 / suff0 / best0：0 的三类统计。

合并左右两段时：pref1 只有当左段整段全是 1 时才能接到右段前缀上，suff1 对称，best1 取"左段最优、右段最优、左段后缀 + 右段前缀"三者最大；0 套公式完全相同。这样线段树的 push_up 与查询合并共用同一套公式。

两种整段修改都能就地结算：

翻转：交换 0/1 两套统计，sum 变为 len - sum；
赋值：直接按目标值构造两套统计。

两个懒标记需要一条优先级规则：赋值覆盖翻转。apply_assign 总是清掉翻转标记；apply_flip 遇到节点已有赋值标记时，改为把赋值目标取反，这样"赋值后翻转"等于"赋相反的初值"，节点上永远不会同时压着两个标记。

合并与翻转示例

这张表用一个区间为 0 0 1 1 的节点演示合并公式与整段翻转（pref 是左前缀、suff 是右后缀、best 是最长连续段）：

节点	内容	sum	pref1	suff1	best1	pref0	suff0	best0
左儿子	0 0	0	0	0	0	2	2	2
右儿子	1 1	2	2	2	2	0	0	0
合并	0 0 1 1	2	0	2	2	2	0	2
翻转后	1 1 0 0	2	2	0	2	0	2	2

看"合并"行：pref1 = 0 因为左段 0 0 不是全 1；suff1 = 2 因为右段全 1，后缀延伸到了左段；best1 = max(0, 2, 0+2) = 2。看"翻转后"行：1 与 0 的两套统计整体交换、sum 不变，best 的数值不变但前缀/后缀归属互换，这就是 apply_flip 只需交换、无需下传的原因。

下面这张表把样例 in1 逐步展开，五种操作的效果一目了然：

操作	动作	状态（10 位）	输出
初始	—	0001101011
1 0 2	赋 1	1111101011
3 0 5	询问 1 个数	1111101011	5
2 2 2	翻转	1101101011
4 0 4	询问最长连续 1	1101101011	2
0 3 6	赋 0	1100000011
2 3 7	翻转	1101111111
4 2 8	询问最长连续 1	1101111111	6
1 0 5	赋 1	1111111111
0 5 6	赋 0	1111100111
3 3 9	询问 1 个数	1111100111	5

观察 4 2 8 这一步：答案 6 是位置 3 到 8 的一整段连续 1，跨过了很多线段树节点，只有靠"左后缀 + 右前缀"的跨界合并才能得到，这正是节点必须维护三类统计的原因。

实现上还有两个容易错的地方：查询跨两个儿子时，合并长度必须用查询实际覆盖的长度（左段到 mid、右段从 mid + 1 开始），不能直接沿用子树整段长度；题目下标从 0 开始，读入后统一 l++、r++ 再进线段树。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-12 22:11
 * update_at: 2026-08-15 22:50
 */
// P2572 [SCOI2010] 序列操作
// 五种操作：区间赋值 0 / 区间赋值 1 / 区间翻转 / 查询区间 1 的个数 / 查询区间最长连续 1。
// 线段树节点同时维护 0/1 两套"前缀 / 后缀 / 最长连续段"统计，双懒标记（赋值覆盖翻转）。
// 题目下标从 0 开始，代码内部统一转换成 1 开始。
#include <bits/stdc++.h>
using namespace std;

// 区间赋值 + 区间翻转 + 区间查询线段树（双懒标记）
struct SegmentTree01 {
    // 线段树节点：0 和 1 两套"前缀 / 后缀 / 最长连续段"统计量，
    // 以及两个懒标记（赋值覆盖翻转，节点上永远只压一个待下传标记）
    struct Node {
        int sum = 0;    // 区间内 1 的个数（查询 3 的答案）
        int pref1 = 0;  // 从区间左端起的最长连续 1 长度
        int suff1 = 0;  // 到区间右端止的最长连续 1 长度
        int best1 = 0;  // 区间内最长连续 1 长度（查询 4 的答案）
        int pref0 = 0;  // 从区间左端起的最长连续 0 长度
        int suff0 = 0;  // 到区间右端止的最长连续 0 长度
        int best0 = 0;  // 区间内最长连续 0 长度
        int assign = -1; // 赋值懒标记：-1 表示没有；0/1 表示整段待赋值
        bool flip = false; // 翻转懒标记：是否有一整段翻转等待下传
    };

    // 左儿子 / 右儿子的节点编号
    static int lson(int p) { return p << 1; }
    static int rson(int p) { return p << 1 | 1; }

    // 区间 [l, r] 的中点
    static int mid(int l, int r) { return (l + r) >> 1; }

    int n = 0;              // 区间大小
    vector<Node> tree;      // 线段树数组

    SegmentTree01(int n = 0) {
        init(n);
    }

    void init(int size) {
        n = size;
        tree.assign(n * 4 + 5, Node{});
    }

    // 把左儿子 a（覆盖长度 lenL）与右儿子 b（覆盖长度 lenR）合并成一个新节点。
    // push_up 与部分区间查询共用这套合并公式。
    Node merge_info(const Node &a, const Node &b, int lenL, int lenR) {
        Node x;
        x.sum = a.sum + b.sum;
        // 左半整段全是 1 时，前缀才能接到右半的前缀上，否则前缀只取左半的。
        x.pref1 = (a.pref1 == lenL) ? lenL + b.pref1 : a.pref1;
        x.suff1 = (b.suff1 == lenR) ? lenR + a.suff1 : b.suff1;
        x.best1 = max(a.best1, max(b.best1, a.suff1 + b.pref1));
        x.pref0 = (a.pref0 == lenL) ? lenL + b.pref0 : a.pref0;
        x.suff0 = (b.suff0 == lenR) ? lenR + a.suff0 : b.suff0;
        x.best0 = max(a.best0, max(b.best0, a.suff0 + b.pref0));
        return x;
    }

    // 上推：用两个孩子合并出当前节点
    void push_up(int p, int l, int r) {
        int m = mid(l, r);
        tree[p] = merge_info(tree[lson(p)], tree[rson(p)], m - l + 1, r - m);
    }

    // 把节点 p 代表的整段区间赋值为 v（0 或 1）：按目标值构造两套统计并打赋值标记。
    // 赋值覆盖翻转：赋值懒标记覆盖掉之前的翻转懒标记。
    void apply_assign(int p, int v, int len) {
        tree[p].sum = v * len;
        tree[p].pref1 = tree[p].suff1 = tree[p].best1 = v * len;
        tree[p].pref0 = tree[p].suff0 = tree[p].best0 = (1 - v) * len;
        tree[p].assign = v;
        tree[p].flip = false;
    }

    // 把节点 p 代表的整段区间翻转：交换 1 / 0 两套统计量，1 的个数变为 len - sum。
    // 懒标记优先级：赋值覆盖翻转。有赋值标记时翻转等价于把赋值目标取反；没有时才累计翻转标记。
    void apply_flip(int p, int len) {
        tree[p].sum = len - tree[p].sum;
        swap(tree[p].pref1, tree[p].pref0);
        swap(tree[p].suff1, tree[p].suff0);
        swap(tree[p].best1, tree[p].best0);
        if (tree[p].assign != -1)
            tree[p].assign ^= 1;
        else
            tree[p].flip = !tree[p].flip;
    }

    // 下推：把节点 p 的懒标记传给两个孩子。先传赋值再传翻转（赋值覆盖翻转）。
    void push_down(int p, int l, int r) {
        if (l == r) return; // 叶子没有儿子，不需要下传

        int m = mid(l, r);
        if (tree[p].assign != -1) {
            apply_assign(lson(p), tree[p].assign, m - l + 1);
            apply_assign(rson(p), tree[p].assign, r - m);
            tree[p].assign = -1;
        }
        if (tree[p].flip) {
            apply_flip(lson(p), m - l + 1);
            apply_flip(rson(p), r - m);
            tree[p].flip = false;
        }
    }

    // 用数组 a 建树（下标从 1 开始）
    void build(const vector<int> &a, int l, int r, int p = 1) {
        if (l == r) {
            apply_assign(p, a[l], 1);
            tree[p].assign = -1; // 叶子不保留懒标记
            return;
        }
        int m = mid(l, r);
        build(a, l, m, lson(p));
        build(a, m + 1, r, rson(p));
        push_up(p, l, r);
    }

    // 区间操作：kind = 0 赋值 0，kind = 1 赋值 1，kind = 2 翻转。
    void update(int ql, int qr, int kind, int l, int r, int p = 1) {
        if (ql <= l && r <= qr) { // 整段命中，就地结算并打懒标记
            if (kind == 2)
                apply_flip(p, r - l + 1);
            else
                apply_assign(p, kind, r - l + 1);
            return;
        }

        push_down(p, l, r);
        int m = mid(l, r);
        if (ql <= m) update(ql, qr, kind, l, m, lson(p));
        if (qr > m) update(ql, qr, kind, m + 1, r, rson(p));
        push_up(p, l, r);
    }

    // 区间查询：返回覆盖 [ql, qr] 的统计量，sum 是 1 的个数、best1 是最长连续 1。
    Node query(int ql, int qr, int l, int r, int p = 1) {
        if (ql <= l && r <= qr) return tree[p];

        push_down(p, l, r);
        int m = mid(l, r);
        if (qr <= m) return query(ql, qr, l, m, lson(p));
        if (ql > m) return query(ql, qr, m + 1, r, rson(p));
        // 查询区间跨两个儿子：分别查询后再合并。
        // 合并用的长度必须是查询实际覆盖部分的长度（左覆盖到 m，右从 m+1 开始）。
        Node a = query(ql, qr, l, m, lson(p));
        Node b = query(ql, qr, m + 1, r, rson(p));
        return merge_info(a, b, m - max(ql, l) + 1, min(qr, r) - m);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    SegmentTree01 seg(n);
    seg.build(a, 1, n);

    while (m--) {
        int op, l, r;
        cin >> op >> l >> r;
        l++; // 题目下标从 0 开始，转成内部 1 开始
        r++;
        if (op <= 2) {
            seg.update(l, r, op, 1, n);
        } else {
            auto res = seg.query(l, r, 1, n);
            if (op == 3)
                cout << res.sum << '\n';   // 区间 1 的个数
            else
                cout << res.best1 << '\n'; // 区间最长连续 1
        }
    }

    return 0;
}

复杂度

时间：建树 $O(n)$ ，单次操作 $O(\log n)$ ，总 $O((n + m) \log n)$ 。
空间：线段树四倍数组（统计量 + 两个懒标记）， $O(n)$ 。

总结

本题是区间赋值、区间翻转、区间求和、区间最长连续段四种操作合一的线段树综合题。它展示了两个进阶要点：一是"查询不是可加信息"时，节点要用前缀 / 后缀 / 最长连续段三件套并用统一公式合并；二是多个懒标记同时存在时，必须显式定义优先级（赋值覆盖翻转），并保证节点上永远只压一个待下传标记。rbook 的《线段树：区间赋值与区间查询》讲解了本解使用的 push_up / apply / push_down 模板结构，本题即由该模板（segtree-range-assign）扩展而来。

图示解析

这张 ASCII 图展示整道题的解题路线：

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20朴素模拟（brute.cpp）
  数组 a[0..n-1] 逐元素赋值 / 取反 / 计数 / 扫描   单次 O(n)
        |
        | 瓶颈：m 次操作 O(n*m)，n, m <= 1e5 不可行
        v
关键观察
  翻转让 0 变 1：只存 1 的统计不够，必须同时维护 0/1 两套对称统计
  整段翻转 = 交换两套统计（1 的个数用 len - sum 结算）
  整段赋值 = 直接构造两套统计
  两个懒标记要有优先级：赋值覆盖翻转
        |
        v
线段树 + 双懒标记（main.cpp）
  节点存 sum, pref1, suff1, best1, pref0, suff0, best0
  懒标记：assign[p]（-1 / 0 / 1）与 flip[p]（bool）
  修改：整段命中就地结算，否则 push_down 后递归两边、回溯 push_up
  查询：整段命中直接返回；跨儿子时按实际覆盖长度合并
        |
        v
复杂度 O((n + m) log n)，空间 O(n)

图中四条主线分别对应"暴力慢在哪"“观察到什么性质”“节点要存什么、两个标记如何协调”“正式解如何实现”。懒标记的本质是把"整段赋值 / 整段翻转"暂停在节点上，等真正要访问子树时才下传；两个标记的先后关系由"赋值覆盖翻转"一条规则唯一确定，这正是本题比普通单懒标记线段树多出的关键思考。