[COCI 2010/2011 #6] STEP

形式化题目

有一个长度为 $n$ 的 0/1 序列，初始所有位置都是 0。给出 $q$ 次操作，每次把位置 $x$ 的值取反（0 变 1，1 变 0）。

每次操作后，输出整个序列中「相邻两个值互不相同」的最长连续子串的长度。要求按顺序输出每次修改后的答案。

思路

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

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/**
 * 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:10
 * update_at: 2026-08-12 22:10
 */
// brute.cpp：小数据暴力解，直接模拟每次翻转并重新扫描最长交替段，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;

int n, q;
int s[MAXN]; // s[i] = 0 表示字符 L，1 表示字符 R

// 重新扫描一遍，统计最长「相邻字符互不相同」的连续段长度。
int longest_alternating() {
    int ans = 1, cur = 1;
    for (int i = 2; i <= n; i++) {
        if (s[i] != s[i - 1])
            cur++;
        else
            cur = 1;
        if (cur > ans)
            ans = cur;
    }
    return ans;
}

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

    cin >> n >> q;
    // 初始序列全部为 L（0）。
    for (int i = 1; i <= n; i++)
        s[i] = 0;

    while (q--) {
        int x;
        cin >> x;
        // 翻转位置 x：L 变 R，R 变 L。
        s[x] ^= 1;

        cout << longest_alternating() << '\n';
    }

    return 0;
}

brute.cpp 直接维护数组 s[]：每次翻转一个位置后，重新从左到右扫描一遍统计最长交替段，单次操作 $O(n)$ ，总复杂度 $O(nq)$ ，无法通过 $2 \times 10^5$ 的数据。

关键观察有两点：

交替只由相邻两个字符是否相同决定。所以「最长交替段」是一个可以像区间和一样合并的信息：只要知道左右两个子区间各自的左端值、右端值、从两端开始的最长交替长、段内最优，就能推出父区间的全部信息。
单点翻转影响面小：只翻转一个位置，在树形结构上看只有从根到该叶子的 $O(\log n)$ 个节点需要重算。

于是用线段树，每个节点维护五元组：

first / last：区间左端、右端的字符值；
pref / suff：从区间左端起 / 到区间右端止的最长交替长度；
best：区间内最长交替长度。

合并（push_up）时只判断一个边界——左子的 last 是否不等于右子的 first：

pref：左子整段交替（pref[左] == 左长）且边界交替时，前缀越过中点延伸成 左长 + pref[右]，否则就是 pref[左]；
suff：右子整段交替（suff[右] == 右长）且边界交替时，后缀越过中点延伸成 右长 + suff[左]，否则就是 suff[右]；
best：max(best[左], best[右], 边界交替 ? suff[左] + pref[右] : 0)。

单点翻转走到叶子后 first ^= 1（last 同步），回溯时逐层 push_up。因为查询区间固定是整个序列，答案就是根节点的 best，连区间查询都不用写。

下面这张表展示样例 2 的完整执行过程（0 表示 L，1 表示 R）：

操作	序列	最长交替段	输出
初始	0 0 0 0 0 0	1
翻转 4	0 0 0 1 0 0	3	3
翻转 1	1 0 0 1 0 0	3	3
翻转 1	0 0 0 1 0 0	3	3
翻转 2	0 1 0 1 0 0	5	5
翻转 6	0 1 0 1 0 1	6	6

观察「翻转 4」与「翻转 6」两行：翻转一个端点字符后，答案可以一下子变多（3 → 5 → 6），因为翻转位置会把两边原来「断掉」的交替段重新接起来。这正是线段树合并时「跨中点拼接」要捕捉的变化。

再看第四次翻转后根节点 [1,6] 的合并过程，这张表展示两个子区间如何拼出父区间：

节点区间	序列	first	pref	suff	best
左 `[1,3]`	0 1 0	0	3	3	3
右 `[4,6]`	1 0 0	1	2	1	2
根 `[1,6]` 合并后	0 1 0 1 0 0	0	5	1	5

看根节点一行：左子整段交替（pref=3 等于区间长 3）且边界 last[左]=0、first[右]=1 不同，所以 pref 延伸为 $3+2=5$ ；跨中点拼接 $suff[左]+pref[右] = 3+2=5$ 成为 best。这就是 push_up 的三条规则在样例上的直接体现。

代码

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/**
 * 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:10
 * update_at: 2026-08-13 11:42
 */
#include <bits/stdc++.h>
using namespace std;

// 节点信息从「区间和」换成「最长交替段」五元组：两端字符 + 最长交替前后缀 + 段内最优。
struct SegmentTreeAlternating {
    // 线段树节点：最长交替段五元组。
    struct Node {
        int first; // 区间左端的字符值（0 表示 L，1 表示 R）
        int last;  // 区间右端的字符值
        int pref;  // 从区间左端起的最长交替段长
        int suff;  // 到区间右端止的最长交替段长
        int best;  // 区间内最长交替段长度
    };

    int n = 0;
    vector<Node> tree; // tree[p] 表示节点 p 的五元组信息

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

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

    // 用左右儿子的信息合并出父节点信息。
    // len_left / len_right 是左右子区间的长度，用于判断某半段是否「整段交替」。
    void push_up(int p, int len_left, int len_right) {
        int left = p << 1, right = p << 1 | 1;
        bool different = (tree[left].last != tree[right].first); // 跨中点的相邻边界是否交替
        tree[p].first = tree[left].first;
        tree[p].last = tree[right].last;

        // 左子整段交替且跨中点边界交替时，前缀可以延伸进右子区间
        if (different && tree[left].pref == len_left)
            tree[p].pref = len_left + tree[right].pref;
        else
            tree[p].pref = tree[left].pref;

        // 右子整段交替且跨中点边界交替时，后缀可以延伸进左子区间
        if (different && tree[right].suff == len_right)
            tree[p].suff = len_right + tree[left].suff;
        else
            tree[p].suff = tree[right].suff;

        // 段内最优：左、右两半各自的最优，或跨过中点的前后缀拼接
        tree[p].best = max(tree[left].best, tree[right].best);
        if (different)
            tree[p].best = max(tree[p].best, tree[left].suff + tree[right].pref);
    }

    // 建树：初始全部为 L（0），单点交替段长度就是 1。
    void build(int l, int r, int p = 1) {
        if (l == r) {
            tree[p].first = tree[p].last = 0;
            tree[p].pref = tree[p].suff = tree[p].best = 1;
            return;
        }
        int mid = (l + r) >> 1;
        build(l, mid, p << 1);
        build(mid + 1, r, p << 1 | 1);
        push_up(p, mid - l + 1, r - mid);
    }

    // 翻转位置 pos：叶子 0/1 取反，再沿路径重新合并所有祖先。
    void flip(int pos, int l, int r, int p = 1) {
        if (l == r) {
            tree[p].first ^= 1; // L 变 R 或 R 变 L
            tree[p].last = tree[p].first;
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid)
            flip(pos, l, mid, p << 1);
        else
            flip(pos, mid + 1, r, p << 1 | 1);
        push_up(p, mid - l + 1, r - mid);
    }

    // 整个序列的最长交替段长度。
    int get_best() const {
        return tree[1].best;
    }
};

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

    int n, q;
    cin >> n >> q;

    SegmentTreeAlternating seg(n);
    seg.build(1, n);

    while (q--) {
        int x;
        cin >> x;
        seg.flip(x, 1, n);
        cout << seg.get_best() << '\n';
    }

    return 0;
}

复杂度

时间：建树 $O(n)$ ；单次翻转只重算一条根到叶子的路径， $O(\log n)$ ；总 $O((n+q) \log n)$ 。
空间：五个四倍大小数组， $O(n)$ 。

总结

「最长交替段」的通用套路是：每个线段树节点维护两端值 + 从两端开始的最长交替长 + 段内最优五个量，合并时只要看跨中点边界是否交替。前缀、后缀能否延伸，取决于相应半段是否整段交替（长度等于区间长）；最优值则要比较左、右、跨中点三种来源。本题翻转是单点的，所以不需要懒标记，只需单点修改后沿路径 push_up——rbook 的《线段树：单点修改与区间查询》讲解了同一种 build / push_up / 单点修改结构，本解即由该模板（segtree-point-add-range-sum）改造而来；与 P3870（区间翻转 + 懒标记）相比，本题多出的核心是 push_up 的合并规则而非懒标记。

图示解析

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

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21朴素模拟（brute.cpp）
  数组 s[1..n]，每次翻转一个位置后重新扫描       O(n) 每次操作
        |
        | 瓶颈：每次操作重扫整个序列，q 次 O(n*q) 太大
        v
关键观察
  交替只由相邻两个字符是否相同决定
  最长交替段可用五元组合并：first/last/pref/suff/best
  单点翻转只影响一条根到叶子的路径
        |
        v
线段树（main.cpp）
  节点存五元组（两端值、最长交替前缀/后缀、段内最优）
   翻转：叶子 0/1 取反，回溯沿路径 push_up
  合并：跨中点边界交替才可拼接
        pref/suff 要求相应半段「整段交替」才能延伸
        best = max(左 best, 右 best, 跨中点拼接)
   答案：根节点 tree[1].best，无需区间查询
        |
        v
复杂度 O((n + q) log n)，空间 O(n)

图中四条主线分别对应「暴力在哪里慢」「观察到什么性质」「五元组如何合并」「正式解如何利用性质」。核心是把「最长交替段」当成一种可合并的区间摘要：修改一个点，只需要在树上一路重新合并 $O(\log n)$ 个祖先节点，根节点的 best 就是每次修改后的答案。