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

Submission #124510386 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #124510696 - Codeforces
Codeforces. Programming competitions and contests, programming community