线段树每个节点只存区间长度与亮灯数,整段取反就是 sum→len-sum,懒标记异或累加,于是区间取反与区间求和都降到 O(log N)。
OJ: roj
题目 ID: 1993
难度:普及+/提高-
标签:数据结构线段树懒标记区间取反区间求和python
创建: 2026-10-08 06:55
更新: 2026-10-08 06:55
形式化题目
有
:区间取反,即对每个 执行 ; :区间查询,输出 ,即区间内亮灯的数量。
每个
样例 1、2。
正解
思路
朴素做法与瓶颈。 直接用布尔数组存每盏灯的状态:操作
瓶颈在于:每次操作都落到单盏灯上。而"区间取反"这个动作,其实并不需要知道区间内部 每一盏灯分别是什么状态。
关键观察:取反对区间和的封闭性。 固定一段长度为
也就是说,只要知道"这段多长"和"这段亮几盏",就能
关键观察:取反是自逆的。 同一段取反两次等于没动,三次等于一次。所以"这段还需要 整体取反"这件事只需要一个布尔量(或者按取反次数的奇偶看成一个 bit), 两次标记叠在一起会互相抵消:
注意这里是异或累加而不是赋值 tag = 1——如果对同一段连续取反两次,
标记必须归零,写成赋值就会多算一次。
这两条观察合起来,正好对上线段树的懒标记模板:每个节点维护
sum(本段亮灯数)与 len(本段长度),区间被完全覆盖时
sum = len - sum; tag ^= 1,否则把标记下传给两个儿子再递归。
为什么不用树状数组 / 分块。 树状数组擅长的是"单点加、区间和"这类线性变换,
而这里的整段变换
下传(push_down)的时机是唯一的易错点。 只要准备往儿子递归——不论是修改还是查询——
就必须先把当前节点的标记落地:两个儿子的 sum 各自按自己的长度取反,
标记各自异或,然后把当前标记清零。查询时也一样要下传,否则儿子手里还是旧数据,
答案会偏小。下传时段的长度务必取子节点自身的长度(mid - l + 1 与 r - mid),
取成父节点长度是这道题最常见的错。
由于灯初始全关,所有节点的 sum 一开始都是 0,所以建树只是把长度填好、再写一遍
- 节点
代表 ,儿子是 与 ,根是 号、代表 ; len不必存成数组——需要它的地方(整段取反)都可以现算, 下传给儿子时则要现算儿子自己的段长。
两版代码都保留了 build(C++)与等价的"数组默认全 0"(Python)两种起步方式,
因为 sum 初值为 0 时
正确性。 对树高归纳:任何时刻,「节点 sum 等于它负责的区间内的真实亮灯数」
与「tag 表示 sum 与 tag,第一式对 sum。
查询只在完全覆盖处取值,取值处的 sum 已在所有祖先标记的作用下被修正过,故答案正确。
代码
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++ 版(同一算法):
/**
* 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;
}复杂度
- 时间:每次操作只会访问
个节点,总时间 。 时约 次节点访问,实测 C++ 约 30 ms(限时 1000 ms)。 Python 版每次操作走的是同样的 条递归路径,只是常数大得多 (递归调用 + 列表下标 + int装箱),10 个真实测试点里最慢的点 8 实测 0.68 s, 贴 1 s 限时但能过;若换成常数更大的 Python 实现仍有 TLE 可能, 但算法与 C++ 同阶,没有做任何降级(未改成暴力、也未用 numpy)。 - 空间:线段树开
个节点,每个节点两个计数与一个标记, 对应分析中 个整数的量级,实测峰值内存 20 MB 以内(限于 131072 KB)。 - 实现对应:
main.cpp与main.py是同一个算法的两版,函数一一对应 (push_down/update对modify/query),C++ 用scanf读入避免 I/O 成为瓶颈, Python 用sys.stdin.buffer.read().split()一次读完再顺序消费。
总结
- 先看变换是不是封闭在一个标量里:长度为
的段取反后亮灯数恰为 , 这是"信息可以只留 sum与len"的根据;找不到这种封闭性,就必须维护更多字段 (例如同时维护"连续 1 的段长"那类题目)。 - 自逆变换的标记用异或累加:
tag ^= 1而不是tag = 1, 两次同段取反必须抵消,这是懒标记类题目最常见的错点。 - 下传与递归必须成对出现:修改和查询在进入儿子之前都要
push_down, 而且儿子按自己的段长取反。 - 本题数据是自造的:素材目录带有
data.py分层生成脚本(按、 递增、 覆盖最小 、全区间 [1,n]、单点区间等边界),题面则是从网络来源完整转录的 一本通《1993 开关switch》。因此数据只能保证与题面一致,出题意图可能与官方原始 测试数据存在偏差;真实数据 10 个点全部通过,与题面描述一致。