Fenwick 维护当前不相交线段的起点，并按秩寻找可能相交的前驱和后继。
OJ: luogu
题目 ID: P2161
难度:提高+/省选-
标签:树状数组有序集合线段python
日期: 2026-07-16 21:00
题意
插入新区间时删除所有与它相交的旧区间并输出删除数；另支持查询当前区间数。
思路
集合中的旧区间始终两两不交，因此按起点有序。日期上界只有 10^5，Fenwick 在每个起点保存是否存在区间，end_at[start] 保存终点。
先找起点不超过新左端的最后一条，检查它是否延伸到左端；再反复找第一个起点不小于左端的区间，直到起点超过新右端。每条被删线段都做一次 Fenwick 删除，最后加入新区间。
Python 知识
- Fenwick 的
kth(rank)用二进制提升实现动态集合按秩查找。 bytes操作码直接与b"B"比较。- 所有历史删除总数不超过插入总数，循环总成本仍是线性的删除次数乘对数。
代码
python
import sys
MAXIMUM = 100000
input = sys.stdin.buffer.readline
tree = [0] * (MAXIMUM + 1)
end_at = [0] * (MAXIMUM + 1)
active = 0
def add(index, delta):
while index <= MAXIMUM:
tree[index] += delta
index += index & -index
def prefix(index):
result = 0
while index:
result += tree[index]
index -= index & -index
return result
def kth(rank):
index = 0
step = 1 << (MAXIMUM.bit_length() - 1)
while step:
target = index + step
if target <= MAXIMUM and tree[target] < rank:
index = target
rank -= tree[target]
step >>= 1
return index + 1
answers = []
for _ in range(int(input())):
operation = input().split()
if operation[0] == b"B":
answers.append(str(active))
continue
left, right = map(int, operation[1:])
removed = 0
before = prefix(left)
if before:
start = kth(before)
if end_at[start] >= left:
add(start, -1)
end_at[start] = 0
active -= 1
removed += 1
while prefix(MAXIMUM) > prefix(left - 1):
start = kth(prefix(left - 1) + 1)
if start > right:
break
add(start, -1)
end_at[start] = 0
active -= 1
removed += 1
add(left, 1)
end_at[left] = right
active += 1
answers.append(str(removed))
print("\n".join(answers))复杂度
每次查找/修改
总结
值域较小时，Fenwick 加按秩查询可以替代平衡树维护动态有序起点集合。