把环形区间展开复制，预处理最远可达区间并用倍增统计覆盖一圈的最少人数。
OJ: luogu
题目 ID: P4155
难度:省选/NOI-
标签:环形区间贪心倍增python
日期: 2026-07-16 18:28
题意
每名战士覆盖圆周上的一段顺时针区间，且没有区间被另一个区间包含。对每名战士，求强制选择他后覆盖整圈所需的最少战士数。
思路
先把跨越编号终点的区间右端加 M，于是每个环形区间都成为直线区间。排序后再复制一份并整体加 M，从任意原区间开始覆盖一圈都变成向右覆盖长度 M。
因为区间之间没有包含关系，按左端排序后右端也严格向右。当前覆盖到 right 时，最优下一步就是选择左端不超过 right 且右端最远的区间。双指针可为每个区间求出这个 next_interval。
对后继映射建立倍增表。强制从区间 start 开始，目标是让覆盖右端达到 start_left + M；从大层向小层跳过仍未到目标的区间，即可得到最少人数。
Python 知识
- 元组列表直接
sort()，会依次按左端、右端和编号排序。 - 列表推导式把所有区间平移
M后追加，实现环转链。 array("i")紧凑保存2n个下标和整张倍增表。map(previous.__getitem__, previous)简洁地计算映射自复合。
代码
python
import sys
from array import array
data = iter(map(int, sys.stdin.buffer.read().split()))
n, circumference = next(data), next(data)
intervals = []
for identity in range(n):
left, right = next(data), next(data)
if right < left:
right += circumference
intervals.append((left, right, identity))
intervals.sort()
intervals += [(left + circumference, right + circumference, identity)
for left, right, identity in intervals]
size = 2 * n
next_interval = array("i", [0]) * size
right_pointer = 0
for i, (_, right, _) in enumerate(intervals):
right_pointer = max(right_pointer, i)
while right_pointer + 1 < size and intervals[right_pointer + 1][0] <= right:
right_pointer += 1
next_interval[i] = right_pointer
jump = [next_interval]
for _ in range(1, n.bit_length() + 1):
previous = jump[-1]
jump.append(array("i", map(previous.__getitem__, previous)))
answer = [0] * n
for start in range(n):
limit = intervals[start][0] + circumference
current = start
used = 1
for level in range(len(jump) - 1, -1, -1):
destination = jump[level][current]
if intervals[destination][1] < limit:
current = destination
used += 1 << level
answer[intervals[start][2]] = used + 1
print(*answer)复杂度
排序
总结
处理环形覆盖时，复制一圈把它展开成直线；处理重复的最优后继时，再用倍增加速。