开关switch

GitHub跳转原题关系图返回列表

线段树每个节点只存区间长度与亮灯数,整段取反就是 sum→len-sum,懒标记异或累加,于是区间取反与区间求和都降到 O(log N)。

OJ: roj

题目 ID: 1993

难度:普及+/提高-

标签:数据结构线段树懒标记区间取反区间求和python

创建: 2026-10-08 06:55

更新: 2026-10-08 06:55

形式化题目

有 NN 盏灯排成一排,初始全部关闭。把灯的状态写成长度 NN 的 01 序列 a1a2⋯aNa_1 a_2 \cdots a_N(ai=1a_i = 1 表示第 ii 盏灯亮着)。依次执行 MM 个操作, 每个操作用三元组 (c,l,r)(c, l, r) 描述,其中 1⩽l⩽r⩽N1 \leqslant l \leqslant r \leqslant N:

  • c=0c = 0:区间取反,即对每个 l⩽i⩽rl \leqslant i \leqslant r 执行 ai←1−aia_i \leftarrow 1 - a_i;
  • c=1c = 1:区间查询,输出 ∑i=lrai\sum_{i=l}^{r} a_i,即区间内亮灯的数量。

每个 c=1c = 1 的操作都要立刻输出一行答案。数据范围 2⩽N⩽1052 \leqslant N \leqslant 10^5、 1⩽M⩽1051 \leqslant M \leqslant 10^5,限时 1000 ms、内存 131072 KB。

样例 N=4N = 4,操作依次为「取反 [1,2][1,2]」「取反 [2,4][2,4]」「查询 [2,3][2,3]」 「取反 [2,4][2,4]」「查询 [1,4][1,4]」。序列的变化是 0000→1100→1011→11000000 \to 1100 \to 1011 \to 1100,其中第三、第五个操作各输出一次查询结果: 查询 [2,3][2,3] 时序列为 10111011,第 2、3 位是 00 与 11,和为 11; 查询 [1,4][1,4] 时序列为 11001100,和为 22。对应样例输出两行 1、2。

正解

思路

朴素做法与瓶颈。 直接用布尔数组存每盏灯的状态:操作 c=0c=0 就循环把 [l,r][l,r] 里每个 元素取反,c=1c=1 就循环累加 [l,r][l,r]。单次操作 O(N)O(N),最坏(每次都是 [1,N][1,N]) 总代价 O(NM)=1010O(NM) = 10^{10} 次基本运算,1 秒内绝无可能跑完。

瓶颈在于:每次操作都落到单盏灯上。而"区间取反"这个动作,其实并不需要知道区间内部 每一盏灯分别是什么状态。

关键观察:取反对区间和的封闭性。 固定一段长度为 LL 的区间,设其中亮灯数为 kk。 取反后:原来亮的 kk 盏全灭,原来灭的 L−kL-k 盏全亮,所以

取反后亮灯数=L−k.\text{取反后亮灯数} = L - k.

也就是说,只要知道"这段多长"和"这段亮几盏",就能 O(1)O(1) 算出整段取反后的亮灯数, 内部的具体排列完全不需要暴露出来。这正是把区间整体变换压成一个标量的典型信号。

关键观察:取反是自逆的。 同一段取反两次等于没动,三次等于一次。所以"这段还需要 整体取反"这件事只需要一个布尔量(或者按取反次数的奇偶看成一个 bit), 两次标记叠在一起会互相抵消:

tag←tag⊕1.\text{tag} \leftarrow \text{tag} \oplus 1.

注意这里是异或累加而不是赋值 tag = 1——如果对同一段连续取反两次, 标记必须归零,写成赋值就会多算一次。

这两条观察合起来,正好对上线段树的懒标记模板:每个节点维护 sum(本段亮灯数)与 len(本段长度),区间被完全覆盖时 sum = len - sum; tag ^= 1,否则把标记下传给两个儿子再递归。

为什么不用树状数组 / 分块。 树状数组擅长的是"单点加、区间和"这类线性变换, 而这里的整段变换 k↦L−kk \mapsto L - k 依赖段长 LL,不是加法,套不进树状数组的差分结构。 分块是 O(MN)≈3×107O(M\sqrt{N}) \approx 3 \times 10^7,能过但不优,而且"整块取反 + 零散块暴力" 要额外维护每个块内的亮灯数。线段树天然按区间二分,配合懒标记正好做到 O(log⁡N)O(\log N), 实现也不比分块长,是这道题的标准选择。

下传(push_down)的时机是唯一的易错点。 只要准备往儿子递归——不论是修改还是查询—— 就必须先把当前节点的标记落地:两个儿子的 sum 各自按自己的长度取反, 标记各自异或,然后把当前标记清零。查询时也一样要下传,否则儿子手里还是旧数据, 答案会偏小。下传时段的长度务必取子节点自身的长度(mid - l + 1 与 r - mid), 取成父节点长度是这道题最常见的错。

由于灯初始全关,所有节点的 sum 一开始都是 0,所以建树只是把长度填好、再写一遍 O(N)O(N) 的递归,也可以直接省掉:

  • 节点 uu 代表 [l,r][l, r],儿子是 2u2u 与 2u+12u+1,根是 11 号、代表 [1,N][1, N];
  • len 不必存成数组——需要它的地方(整段取反)都可以现算 r−l+1r - l + 1, 下传给儿子时则要现算儿子自己的段长。

两版代码都保留了 build(C++)与等价的"数组默认全 0"(Python)两种起步方式, 因为 sum 初值为 0 时 k↦L−kk \mapsto L - k 退化成了 k↦Lk \mapsto L,两种写法等价。

正确性。 对树高归纳:任何时刻,「节点 uu 的 sum 等于它负责的区间内的真实亮灯数」 与「uu 的 tag 表示 uu 的整段相对儿子多做了奇数次取反」两条不变式同时成立。 完全覆盖时只改 sum 与 tag,第一式对 uu 成立;下传时把标记那一次取反 按 k↦L−kk \mapsto L-k 精确地补给两个儿子,两式都不破;回溯时用儿子之和刷新 sum。 查询只在完全覆盖处取值,取值处的 sum 已在所有祖先标记的作用下被修正过,故答案正确。

代码

Python 版:

python
#!/usr/bin/env python3
# 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-10-08 06:55
# update_at: 2026-10-08 06:55

import sys


def push_down(u: int, l: int, r: int, seg: list[int], tag: list[int]) -> None:
    """把 u 的待取反标记下传给两个儿子,各自按自己的段长取反。

    只在往儿子递归之前调用,此时必有 l < r,所以儿子编号一定在数组范围内。
    """
    if not tag[u]:
        return
    mid, left, right = (l + r) >> 1, u << 1, u << 1 | 1
    seg[left] = (mid - l + 1) - seg[left]     # 左儿子的段长是 mid-l+1
    seg[right] = (r - mid) - seg[right]       # 右儿子的段长是 r-mid
    tag[left] ^= 1
    tag[right] ^= 1
    tag[u] = 0


def modify(u: int, l: int, r: int, ql: int, qr: int, seg: list[int], tag: list[int]) -> None:
    """把 [ql, qr] 内的灯全部取反:整段被覆盖时只改本节点并打标记,否则下传后递归。"""
    if ql <= l and r <= qr:
        seg[u] = (r - l + 1) - seg[u]  # 段长 len 内有 seg[u] 盏灯亮,取反后剩 len-seg[u]
        tag[u] ^= 1                    # 两次取反互相抵消,所以是异或而不是赋值
        return
    push_down(u, l, r, seg, tag)
    mid = (l + r) >> 1
    if ql <= mid:
        modify(u << 1, l, mid, ql, qr, seg, tag)
    if qr > mid:
        modify(u << 1 | 1, mid + 1, r, ql, qr, seg, tag)
    seg[u] = seg[u << 1] + seg[u << 1 | 1]  # 回溯时用儿子的新值更新自己


def query(u: int, l: int, r: int, ql: int, qr: int, seg: list[int], tag: list[int]) -> int:
    """返回 [ql, qr] 内开着的灯数。"""
    if ql <= l and r <= qr:
        return seg[u]
    push_down(u, l, r, seg, tag)
    mid = (l + r) >> 1
    res = 0
    if ql <= mid:
        res += query(u << 1, l, mid, ql, qr, seg, tag)
    if qr > mid:
        res += query(u << 1 | 1, mid + 1, r, ql, qr, seg, tag)
    return res


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)

    # 灯初始全关,所以初始 sum 全是 0,不需要递归建树,只把数组开出来即可;
    # 节点 1 代表 [1, n],节点 u 的两个儿子是 2u、2u+1,深度 O(log n) 不担心容量。
    seg = [0] * (4 * n + 5)  # seg[u] = u 这段区间内开着的灯数
    tag = [0] * (4 * n + 5)  # tag[u] = 1 表示 u 这段整体还需要取反一次

    out: list[str] = []
    for _ in range(m):
        c, a, b = next(data), next(data), next(data)
        if c == 0:
            modify(1, 1, n, a, b, seg, tag)  # 第一种操作:区间取反
        else:
            out.append(str(query(1, 1, n, a, b, seg, tag)))  # 第二种操作:输出亮灯数

    sys.stdout.write('\n'.join(out) + ('\n' if out else ''))


if __name__ == "__main__":
    solve()

C++ 版(同一算法):

cpp
/**
 * 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-10-08 06:55
 * update_at: 2026-10-08 06:55
 */
// 一本通 1993 开关switch:区间取反 + 区间求和,带懒标记的线段树
// 核心性质:长度为 len 的区间里有 sum 盏灯亮着,整段取反后亮灯数就是 len - sum,
// 所以每个节点只需要维护 len 与 sum,取反操作可以整段 O(1) 完成。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 100000 + 5;

ll n, m;  // 灯的数目、操作的数目

struct Node {
    ll sum;    // 本段区间内开着的灯数
    ll len;    // 本段区间的长度,用于整段取反:sum -> len - sum
    char tag;  // 懒标记:1 表示本段整体还需要取反一次,0 表示不需要(取反两次互相抵消)
};
Node node[MAXN * 4];  // 线段树节点,u 的两个儿子是 u<<1 与 u<<1|1

// 建树:灯初始全关,所以所有节点的 sum 都是 0,只需把长度与标记填好
void build(int u, ll l, ll r) {
    node[u].sum = 0;
    node[u].len = r - l + 1;
    node[u].tag = 0;
    if (l == r) return;
    ll mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
}

// 把 u 的懒标记下传给两个儿子:它们各自按"自己的长度"取反,标记异或累加
void push_down(int u) {
    if (node[u].tag == 0) return;
    int left = u << 1, right = u << 1 | 1;
    node[left].sum = node[left].len - node[left].sum;      // 左儿子按自己的长度取反
    node[right].sum = node[right].len - node[right].sum;   // 右儿子按自己的长度取反
    node[left].tag ^= 1;
    node[right].tag ^= 1;
    node[u].tag = 0;
}

// 区间取反:把 [ql, qr] 内每盏灯的状态反转
void update(int u, ll l, ll r, ll ql, ll qr) {
    if (ql <= l && r <= qr) {
        node[u].sum = node[u].len - node[u].sum;  // 整段被覆盖:亮灯数变成 len - sum
        node[u].tag ^= 1;
        return;
    }
    push_down(u);  // 要往儿子走了,标记必须先落地
    ll mid = (l + r) >> 1;
    if (ql <= mid) update(u << 1, l, mid, ql, qr);
    if (qr > mid) update(u << 1 | 1, mid + 1, r, ql, qr);
    node[u].sum = node[u << 1].sum + node[u << 1 | 1].sum;  // 回溯时用儿子的新值更新自己
}

// 区间查询:返回 [ql, qr] 内开着的灯数
ll query(int u, ll l, ll r, ll ql, ll qr) {
    if (ql <= l && r <= qr) return node[u].sum;
    push_down(u);
    ll mid = (l + r) >> 1, res = 0;
    if (ql <= mid) res += query(u << 1, l, mid, ql, qr);
    if (qr > mid) res += query(u << 1 | 1, mid + 1, r, ql, qr);
    return res;
}

int main() {
    scanf("%lld %lld", &n, &m);
    build(1, 1, n);
    for (ll i = 1; i <= m; i++) {
        ll c, a, b;
        scanf("%lld %lld %lld", &c, &a, &b);
        if (c == 0)
            update(1, 1, n, a, b);  // 第一种操作:区间取反
        else
            printf("%lld\n", query(1, 1, n, a, b));  // 第二种操作:输出该区间亮灯数
    }
    return 0;
}

复杂度

  • 时间:每次操作只会访问 O(log⁡N)O(\log N) 个节点,总时间 O((N+M)log⁡N)O((N + M) \log N)。 N=M=105N = M = 10^5 时约 1.7×1061.7 \times 10^6 次节点访问,实测 C++ 约 30 ms(限时 1000 ms)。 Python 版每次操作走的是同样的 O(log⁡N)O(\log N) 条递归路径,只是常数大得多 (递归调用 + 列表下标 + int 装箱),10 个真实测试点里最慢的点 8 实测 0.68 s, 贴 1 s 限时但能过;若换成常数更大的 Python 实现仍有 TLE 可能, 但算法与 C++ 同阶,没有做任何降级(未改成 O(NM)O(NM) 暴力、也未用 numpy)。
  • 空间:线段树开 4N4N 个节点,每个节点两个计数与一个标记, 对应分析中 4×1054 \times 10^5 个整数的量级,实测峰值内存 20 MB 以内(限于 131072 KB)。
  • 实现对应:main.cpp 与 main.py 是同一个算法的两版,函数一一对应 (push_down / update 对 modify / query),C++ 用 scanf 读入避免 I/O 成为瓶颈, Python 用 sys.stdin.buffer.read().split() 一次读完再顺序消费。

总结

  • 先看变换是不是封闭在一个标量里:长度为 LL 的段取反后亮灯数恰为 L−kL - k, 这是"信息可以只留 sum 与 len"的根据;找不到这种封闭性,就必须维护更多字段 (例如同时维护"连续 1 的段长"那类题目)。
  • 自逆变换的标记用异或累加:tag ^= 1 而不是 tag = 1, 两次同段取反必须抵消,这是懒标记类题目最常见的错点。
  • 下传与递归必须成对出现:修改和查询在进入儿子之前都要 push_down, 而且儿子按自己的段长取反。
  • 本题数据是自造的:素材目录带有 data.py 分层生成脚本(按 NN、MM 递增、 覆盖最小 N=2N=2、全区间 [1,n]、单点区间等边界),题面则是从网络来源完整转录的 一本通《1993 开关switch》。因此数据只能保证与题面一致,出题意图可能与官方原始 测试数据存在偏差;真实数据 10 个点全部通过,与题面描述一致。