国旗计划：解法与证明

思路

若区间终点在起点的逆时针方向，就给终点加上 $M$，从而把每个圆环区间表示成数轴上的区间。按起点排序后，再复制一份区间，并给复制区间的起点和终点都加上 $M$。

题目保证区间互不包含，因此按起点递增排序时，终点也严格递增。固定某个原区间作为必须参加的第一棒后，覆盖整个圆环等价于从该区间起点出发，在线段上连续覆盖到“起点加 $M$”。

做法

设当前已经覆盖到坐标 $R$。下一名战士的起点必须不超过 $R$。在所有可接力区间中选择终点最远者不会变差：把任意方案的下一段替换成该区间后，覆盖范围只会扩大，后续选择仍然可用。因此每一步都选择可达区间中终点最远者。

由于排序后终点严格递增，最远终点对应起点不超过 $R$ 的最右区间。使用双指针可为每个区间预处理贪心后继 $nxt_i$。

再预处理 $up_{k,i}$，表示从区间 $i$ 连续执行 $2^k$ 次贪心接力后到达的区间。对每个原区间，从高位到低位执行仍不能达到目标的跳跃，最后再接一棒，即可得到最少总人数。答案按输入中的原编号恢复。

正确性证明

圆环展开后，任何包含指定强制区间的覆盖方案都可以依顺时针接力顺序写成从其起点覆盖到起点加 $M$ 的线段方案，反之亦然。

在任意当前覆盖终点下，最远终点贪心可替换任意最优方案的下一段而不增加人数。归纳可得反复贪心使用的区间数最少。倍增只是在同一条贪心后继链上批量执行跳跃，不改变任何选择，所以最终答案正确。

复杂度

排序、倍增预处理及全部查询的总时间复杂度为 $O(N\log N)$，空间复杂度为 $O(N\log N)$。复制后的坐标小于 $2M<2\times10^9$，实现中使用 64 位整数。

部分分方法

当 $N\le1000$ 时，可对每个强制区间独立沿贪心接力扫描，整体复杂度为 $O(N^2)$。

若所有强制答案都不超过 $100$，统一预处理贪心后继后，对每个起点直接沿后继链行走即可，总时间复杂度为 $O(N\log N+100N)$，空间复杂度为 $O(N)$。