[ICPC2017 WF] Scenery

提供一个 \(O(n^2\alpha(n))\) 的做法。

这种匹配问题如果直接寻找最优的匹配方式是困难的，因为 \(\geqslant k\) 的限制，当前匹配的点会对之后的产生不小的影响。但是如果我们 \(\text{fix}\) 好了一个选择的升序位置序列 \(a\)，想要判定其是否合法是容易的，需要以下两个条件：

\(1.\) 对于 \(i\in [1,n-1]\cap Z\)，\(a_{i+1}-a_{i}\geqslant k\)。

\(2.\) 对于一个区间的子集 \(S\)，其并集 \(N(S)\) 中 \(a\) 的元素个数要大于等于 \(|S|\)，而我们仅需 \(\text{check}\) 并集为一个区间的就合法，所以可以得到 \(O(n^2)\) 个区间有关的约束。

实际上可以发现现在只有对前缀和的约束了(\(1\) 相当于限制 \(s_{i}-s_{i-k}\leqslant 1\))，但由于值域比较大，需要离散化，此时相当于 \(s_{y}-s_{x}\leqslant \lceil\frac{y-x}{k}\rceil\)。

直接跑最短路肯定不行，但是我们连出的边其实很有性质，可以对 \(\text{Bellman ford}\) 算法进行优化，关键在于优化 \(\geqslant k\) 与 \(\text{Hall}\) 定理得到的若干个区间约束的部分：

\(1.\) \(\geqslant k\) 的 \(\lceil\frac{y-x}{k}\rceil\) 可以写为 \(\lfloor\frac{y}{k}\rfloor-\lfloor\frac{x}{k}\rfloor+[y\mod k> x\mod k]\)，此时由于后面的式子至多贡献 \(1\)，保留 \(dp_{x}-\lfloor\frac{x}{k}\rfloor\) 最小其次 \(x\mod k\) 最大的状态一定最优。

\(2.\) \(s_{y}-s_{x}\geqslant [x,y]\) 内的区间个数，这个倒序扫描后实际上就是后缀 \(-1\)，在前面添加元素，与查询全局最小值，这个是反向决策单调性，后面的元素比前面优了就一直会比前面优，此时可以用并查集合并两个元素，在并查集上的每一个元素存下单调栈的差分数组，每次修改时使对应并查集的差分数组 \(-1\)，如果一个位置的差分数组 \(<0\)，则可以将前面的一个元素合并到后面。

复杂度 \(O(n^2\alpha (n))\)，由于并查集常数较大，需要加一些减枝才能通过。