[TJOI2009] 开关

形式化题目

有一个长度为 $n$ 的 0/1 序列，初始所有位置都是 0。给出 $m$ 次操作：

把区间 $[a,b]$ 内的每个值取反（0 变 1，1 变 0）；
询问区间 $[a,b]$ 内值为 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/**
 * 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 21:48
 * update_at: 2026-08-12 21:48
 */
// brute.cpp：小数据暴力解，直接维护每盏灯的状态，用来理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;

int n, m;
bool lamp[MAXN]; // lamp[i] = true 表示第 i 盏灯是亮的

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

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int c, a, b;
        cin >> c >> a >> b;
        if (c == 0) {
            // 区间取反：暴力逐盏翻转。
            for (int j = a; j <= b; j++)
                lamp[j] = !lamp[j];
        } else {
            // 区间查询：暴力数亮灯数量。
            int cnt = 0;
            for (int j = a; j <= b; j++)
                if (lamp[j])
                    cnt++;
            cout << cnt << '\n';
        }
    }
    return 0;
}

brute.cpp 直接维护数组 lamp[]：区间翻转逐盏取反，区间查询逐盏计数，单次操作 $O(n)$ ，总复杂度 $O(nm)$ ，无法通过 $10^5$ 的数据。

关键观察有两点：

翻转的自逆性：同一个位置翻转两次等于不翻，所以懒标记只要一个 bool，合并规则就是异或。
整段翻转可以整体结算：长度为 len 的区间亮灯数量为 sum，整体取反后数量变成 len - sum，不需要逐个访问叶子。

于是用线段树 + 懒标记：每个节点存这段区间内亮灯的数量；区间翻转完全覆盖一个节点时，只改这个节点的数量和标记，把翻转“欠”在节点上；之后要进入它的子树时，再把标记下传给两个儿子。

数学视角：为什么懒标记能成立

把上面的观察用代数语言压缩，可以得到懒标记成立的精确条件：

查询信息构成幺半群：区间和用 $+$ 合并， $+$ 满足结合律，且存在单位元 $0$ （空区间的和、查询累加的初始值），所以区间和构成交换幺半群 $(\mathbb{Z}, +, 0)$ 。
翻转是摘要上的自同态：翻转可以仅凭节点摘要结算， $\text{flip}(\text{sum}) = \text{len} - \text{sum}$ ，并且能与合并操作交换：

\text{flip}(a+b) = \text{len} - (a+b) = (\text{len}_A - a) + (\text{len}_B - b) = \text{flip}(a) + \text{flip}(b)

这就是“翻转不必下到叶子”的数学原因。又因为 $\text{flip} \circ \text{flip} = \text{id}$ （翻转自逆），懒标记可以用 bool 异或合并。

一句话概括：查询信息构成幺半群，且区间更新是幺半群上的自同态，就可以用懒标记线段树维护。反过来，如果更新依赖区间内部的具体值（例如“把区间内每个数换成它的后继”），它就不是摘要自同态，懒标记会失效。

下面这张图展示一棵规模为 4 的线段树，节点上的数字是它代表的区间：

任意操作区间都能拆成 $O(\log n)$ 个“整段节点”。例如查询/翻转 $[2,4]$ 会命中 [2,2] 和 [3,4] 这两个整段节点，各花 $O(1)$ 结算，这就是 $O(\log n)$ 的来源：不需要访问区间内的每个点。

以样例为例，4 盏灯每次操作后的真实状态如下：

操作	灯 1 2 3 4	输出
初始	0 0 0 0
翻转 [1,2]	1 1 0 0
翻转 [2,4]	1 0 1 1
查询 [2,3]	1 0 1 1	1
翻转 [2,4]	1 1 0 0
查询 [1,4]	1 1 0 0	2

观察表中两次翻转 $[2,4]$ ：第一次后该段从 0 1 1 变 1 0 0，第二次又恢复原样。这正是节点数量公式 len - sum 和懒标记异或（翻两次抵消）在样例上的直接体现。

代码

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/**
 * 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 21:54
 * update_at: 2026-08-12 21:54
 */
#include <bits/stdc++.h>
using namespace std;

// 仿照 rbook 模板 segtree-range-assign 的 pull/apply/push 结构，
// 把「区间赋值」改为「区间翻转」：整段数量取反，懒标记用 bool 异或。
struct SegmentTreeRangeFlip {
    int n = 0;
    vector<int> tree;   // tree[p] 表示节点 p 区间内亮灯的数量
    vector<bool> lazy;  // lazy[p] 表示节点 p 区间是否整段待翻转

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

    void init(int size) {
        n = size;
        tree.assign(n * 4 + 5, 0); // 初始全灭，整棵树隐含为全 0，不需要 build
        lazy.assign(n * 4 + 5, false);
    }

    // 把两个儿子的信息合并回父节点。
    void pull(int p) {
        tree[p] = tree[p << 1] + tree[p << 1 | 1];
    }

    // 把节点 p 代表的整段区间 [l, r] 翻转：亮灯数量变为 长度 - 亮灯数量。
    void apply(int p, int l, int r) {
        tree[p] = (r - l + 1) - tree[p];
        lazy[p] = !lazy[p];
    }

    // 下传节点 p 的翻转懒标记到两个儿子。
    void push(int p, int l, int r) {
        if (!lazy[p] || l == r) return;

        int mid = (l + r) >> 1;
        apply(p << 1, l, mid);
        apply(p << 1 | 1, mid + 1, r);
        lazy[p] = false;
    }

    // 把区间 [ql, qr] 整体取反。
    void flip_range(int ql, int qr, int l, int r, int p = 1) {
        if (ql <= l && r <= qr) {
            apply(p, l, r);
            return;
        }

        push(p, l, r);
        int mid = (l + r) >> 1;
        if (ql <= mid) flip_range(ql, qr, l, mid, p << 1);
        if (qr > mid) flip_range(ql, qr, mid + 1, r, p << 1 | 1);
        pull(p);
    }

    // 查询区间 [ql, qr] 内亮灯的数量。
    int query(int ql, int qr, int l, int r, int p = 1) {
        if (ql <= l && r <= qr) return tree[p];

        push(p, l, r);
        int mid = (l + r) >> 1;
        int answer = 0;
        if (ql <= mid) answer += query(ql, qr, l, mid, p << 1);
        if (qr > mid) answer += query(ql, qr, mid + 1, r, p << 1 | 1);
        return answer;
    }
};

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

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

    SegmentTreeRangeFlip seg(n); // 初始全部关着，无需 build

    while (m--) {
        int c, a, b;
        cin >> c >> a >> b;
        if (c == 0)
            seg.flip_range(a, b, 1, n);
        else
            cout << seg.query(a, b, 1, n) << '\n';
    }

    return 0;
}

复杂度

时间：单次操作 $O(\log n)$ ，总 $O(m \log n)$ 。
空间：线段树四倍数组， $O(n)$ 。

总结

这道题是区间翻转懒标记最标准的模板：数量用 len - sum 结算，标记用异或合并。“翻转两次抵消”是布尔懒标记的典型合并规则；理解了 apply + push 的写法，就掌握了线段树处理区间翻转类问题的核心套路。rbook 的《线段树：区间赋值与区间查询》讲解了同一种 pull / apply / push 模板结构，本解即由该模板（segtree-range-assign）改造而来。

图示解析

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

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18朴素模拟（brute.cpp）
  数组 lamp[1..n] 逐盏翻转 / 逐盏计数      O(n) 每次操作
        |
        | 瓶颈：单次操作 O(n)，m 次操作 O(n*m) 太大
        v
关键观察
  区间翻转 = 区间内 1 的数量变成长度减原数量
  同一个点翻转两次等于没翻（取反的自逆性）
        |
        v
线段树 + 懒标记（main.cpp）
  节点存区间内亮灯数量 sum
  懒标记 lazy 表示整段待翻转（异或合并）
  翻转：整段直接 sum = len - sum，标记取反，不下传
  查询：遇到标记先下传，再进子树
        |
        v
复杂度 O((n + m) log n)，空间 O(n)

图中三条主线分别对应“暴力在哪里慢”“观察到什么性质”“正式解如何利用这个性质”。懒标记的本质是把“整段翻转”这个操作暂停在节点上，等真正要访问子树时才往下传，从而让一次操作只走一条树链。

目录

形式化题目

思路

数学视角：为什么懒标记能成立

代码

复杂度

总结

图示解析