CF2018E2 Solution

CF2018E2 Solution

先考虑E1的做法。

首先我们如果钦定一组 \(k\) 条线段的话，容易求出最大组数。

简单来讲就是将所有端点按照右端点排序，这样只需要考虑一个偏序，然后扫描，将区间 \([l_i,r_i]\) 加一，当发现某个点的值为 \(k\) 时，就说明分成了一组方案。

此时我们一定清空，然后记录当前的 \(r\)，也就是后面选的点左端点不得小于等于 \(r\)。

直觉上，这样贪心选择一定更优。设这样的答案为 \(k\)。

我们的答案可以表示为 \(\max k·f(k)\)。

而我们发现，对于一个固定的 \(f(k)\)，它是随着 \(k\) 单调不升的，这很显然。

所以对于一个固定的 \(f(k)\)，可以通过二分的形式得到 \(\max k\)，这样就足以在 \(O(n\log n\sqrt{n\log n})\) 解决问题，足以通过 E1。

事实上在这里可以通过整体二分求得所有的 \(f(k)\)，它的复杂度足以降至 \(O(n^{1.5}\log n)\)，这是因为在第 \(d\) 层时，值域被划分为了 \(O(\frac{n}{2^d})\) 长的 \(2^d\) 段，在 \([\frac{n}{2^{d/2}},n]\) 范围内 \(f\le 2^{d/2}\)，而 \([1,\frac{n}{2^{d/2}}]\) 又仅有 \(O(2^{d/2})\) 段，所以这里总段数是 \(O(2^{d/2})\) 的，总的整体二分复杂度就是 \(O(\sum^{\log_2n} 2^{d/2})=O(\sqrt n)\) 的。

那么考虑优化线段树这个过程，一个很重要的技巧是，我们只关心全局最大值，以及后缀加。

那么可以使用并查集，维护后缀最大值出现位置。

首先，我们使端点互不相同，具体地，将原本的所有端点排序（如果是相同值，原本为右端点的放在后面），然后依次给其赋值 \(1\sim 2n\)。

这显然不会破坏相交关系也不会新增。

然后我们利用并查集维护差分，每次后缀加只会造成新的 \(r\) 成为一个后缀最大值，以及增加的最大的 \(< l\) 的后缀最大值端点删去。

利用并查集维护这个即可。