P4155 [SCOI2015] 国旗计划

按套路破环成链，要注意右端点小于左端点的区间跨越了 \(N\to 1\)。

假设钦定了士兵 \(i\)，接下来肯定贪心地选择左端点小于等于当前右端点的右端点最大的下一个区间。因为区间不存在包含关系，按右端点从小到大排序后形式化地讲就是找到最大的 \(j\) 使得 \(C_j\leq D_i\)。

直接做是 \(O(N^2)\) 的，但观察到相关决策链构成了决策树，所有决策树构成了决策森林，其中点 \(u\) 的终点为距离 \(u\) 最近的祖先 \(v\) 满足 \(D_v\geq C_u+M\)。

从根结点开始双指针，但上端点移动时需要朝着下端点的方向。这只需要在递归下去前更新边表头就行了，即递归完的子树直接跳过。

使用基数排序后时间复杂度 \(O(N)\)。