用翻转懒标记维护区间开关状态和区间亮灯数量。
OJ: luogu
题目 ID: P3870
难度:普及/提高-
标签:线段树懒标记区间翻转python
日期: 2026-07-16 23:59
题意
初始所有开关关闭，支持区间取反和查询区间内打开的开关数。
思路
节点只需保存区间内 1 的个数。翻转长度为 length 的节点时，新的数量是 length - count；两个翻转标记叠加等于没有翻转，因此懒标记用异或维护。
Python 知识
bytearray适合保存只有0/1的懒标记。tree[node] = length - tree[node]直接完成整段取反。- 把所有答案放进列表，最后一次
"\\n".join输出，减少频繁刷新。
代码
python
import sys
sys.setrecursionlimit(1_000_000)
input = sys.stdin.buffer.readline
n, operations = map(int, input().split())
tree = [0] * (4 * n)
flipped = bytearray(4 * n)
def apply(node, length):
tree[node] = length - tree[node]
flipped[node] ^= 1
def push(node, left, right):
if flipped[node] and left != right:
middle = (left + right) // 2
apply(node * 2, middle - left + 1)
apply(node * 2 + 1, right - middle)
flipped[node] = 0
def update(node, left, right, query_left, query_right):
if query_left <= left and right <= query_right:
apply(node, right - left + 1)
return
push(node, left, right)
middle = (left + right) // 2
if query_left <= middle:
update(node * 2, left, middle, query_left, query_right)
if middle < query_right:
update(node * 2 + 1, middle + 1, right, query_left, query_right)
tree[node] = tree[node * 2] + tree[node * 2 + 1]
def query(node, left, right, query_left, query_right):
if query_left <= left and right <= query_right:
return tree[node]
push(node, left, right)
middle = (left + right) // 2
answer = 0
if query_left <= middle:
answer += query(node * 2, left, middle, query_left, query_right)
if middle < query_right:
answer += query(node * 2 + 1, middle + 1, right, query_left, query_right)
return answer
answers = []
for _ in range(operations):
operation, left, right = map(int, input().split())
if operation == 0:
update(1, 1, n, left, right)
else:
answers.append(str(query(1, 1, n, left, right)))
print("\n".join(answers))原有 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-07-16 23:46
* update_at: 2026-07-16 23:46
*/
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
return 0;
}复杂度
建树隐含为全零，单次修改或查询 O(log n)，空间 O(n)。
总结
“翻转两次抵消”是布尔懒标记最典型的合并规则。