P5609 [Ynoi2013] 对数据结构的爱

题面传送门

好像搞了个神秘做法。

考虑离线扫描线，用一个 fhq-Treap 维护所有的询问现在长什么样，然后每次操作就整体加 \(A_i\)，\(\geq p\) 的减去 \(p\)，这个可以分裂之后打整体标记，然后用那个值域相交的 fhq-Treap 合并实现。

然后你发现这样就过了。

构造一下卡不掉，于是考虑给这个东西编一个势能。

设现在 fhq-Treap 维护的东西为 \(a\) 序列，定其势能为 \(\sum\limits_{i=1}^{n-1}{\log(a_{i+1}-a_i)}\)，容易发现的是总势能不会超过\(O(m\log V)\)，因此我们来考虑减少一个势能的代价。

fhq-Treap 可以在连续段个数乘以 \(\log\) 的时间复杂度内合并两个值域相交的集合，这里连续段指的是合并完之后极长连续的一段满足来自同一边。我们考虑一个最简单的情形，假设其中一个集合为 \(a_1,a_2,a_3\)，另一个集合为 \(b_1,b_2\)，合并后为 \(a_1,b_1,a_2,b_2,a_3\)。

原来的势能为 \(\log(a_2-a_1)+\log(a_3-a_2)+\log(b_2-b_1)\)。考虑 \(\min(\log(a_2-b_1),\log(b_2-a_2))\leq \log(b_2-a_2)-1\)，并且 \(\log(b_1-a_1)\leq\log(a_2-a_1),\log(a_3-b_2)\leq \log(a_3-a_2)\)，所以总势能至多增加 \(O(\log n)-1\)。

进一步容易用上面的方法证明，如果最终连续段的个数为 \(S\)，则总势能至多增加 \(O(\log V)-\frac{1}{4}S\)，所以总复杂度 \(O(n\log n+m\log m\log V)\)。

这玩意的劣势在于其复杂度是 \(O(\log V)\) 而不是 \(O(\log m)\)（说不定能证明势能是 \(O(\log m)\) 的），但是优势在于可以对每个点设不同的 \(p\)。因为常数比较大需要卡卡常。

submission