题解 P4064 【[JXOI2017]加法】

2019-03-15 19:53:48


第一眼想到二分答案。 然后我就不会了

首先以 $l$ 为第一关键字、 $r$ 为第二关键字将所有区间排序。

假设现在二分出了一个答案 $mid$ 。

贪心地想,我们只会在不得不给一个区间加上 $a$ 时给它加上 $a$ 。

于是从左到右扫,如果一个点没有达到 $mid$ 的话,那么从之前的区间中选一个加上 $a$ 。

再贪心地想,选出的区间一定是 $r$ 最大的,这样子才能覆盖更多的点。

于是可以用一个堆来维护 $r$ 最大的区间,每次取出即可。

然后还要维护一个树状数组来支持区间加、单点查询。

考虑不可行的情况:

  • 没有线段能够覆盖到当前这个没有达到 $mid$ 的点。
  • 用的次数超过了 $k$ 。

具体实现及细节见代码