Educational Codeforces Round 112 Boring Segments 题解 (Java/C++)

题解

首先，我们注意到最终结果只和w的最大值和最小值有关。这将意味着，只要w在最大值和最小值之间，这个线段加不加进来其实都不会影响。
因此，我们可以立刻想到，我们根据w对所有线段排序。我们考虑对所有的线段从两端做减法，直到再减的话就会导致1-m无法被全覆盖。

以样例为例，我们可以看到，11-12的这一段（黄色部分）其实可有可无，并不影响结果。

于是总的来说，我们每次将R往下移一位，然后尝试将L下移，直到恰好无法移动。这样我们就能快速遍历所有L和R的配对。最后我们只需要取所有w[R]-w[L]的最小值即可。
以下图的操作为例：

于是最后的问题就是怎么快速验证L到R之间的线段是否能够覆盖整个1-m。这里其实非常显然，使用线段树维护即可。

当我们每把一个线段加入L和R之间的时候，我们就把相关区间+1；当我们移除出去的时候，就把相关区间-1。而由于一定要有交集，所以我们添加或删除区间的时候，是按左开有闭操作。

代码

Java

C++