[题解] ABC256H I like Query Problem

· · 题解

ABC256H I like Query Problem

根据颜色段均摊的相关，操作只会产生 O(N) 个颜色段的插入和删除。

记一个颜色为 v 的段的势能为 \log v，这样总势能就是 O(N \log V) 的，每次一操作的时候遍历区间的非零颜色段，每个段的势能至少减少 1。

这样的话如果我们能 O(1) 找到一个需要被修改的段就能做到 O(N \log V) 的复杂度。这可以用平衡树维护来实现：每次将对应区间分裂出来，遍历各段并进行修改，同时注意排除颜色为 0 的段。

bonus：如果有区间加操作怎么做？

记势能函数为 \Phi(x) = \sum \log(\lvert x_i - x_{i+ 1} \rvert)。

先分析一下势能的增加量，每种操作都只会使端点处势能增加，每次增加量不超过 2\log V，因此总势能是 O(N \log V) 的。这样的话如果能以 O(1) 的复杂度让势能减小 1 就赢了。

具体的做法是平衡树维护颜色段，每次区间除操作就先把对应的区间分裂出来并拍平到序列上，遍历每个颜色段暴力修改，并合并相邻的同色段，如果是用 treap 维护的话最后需要将颜色段分治合并回平衡树上。

如果本次操作涉及 m 个颜色段，分治合并的复杂度是 \displaystyle O\left(\sum k \frac{m}{2^k} \right) = O(m) 的，因此可以在 O(\log n + m) 的时间内让势能减少至少 O(m)，也就达成了目标。

时间复杂度同样是 O(N \log V)。

可以发现，原题的做法更充分地利用了题目的形式，使得我们每次区间除之后不需要把相邻同色段合并，而 bonus 部分的做法需要。

代码。