CF1322E - Median Mountain Range - 总结

CF1322E - Median Mountain Range

考虑分别对每个位置求出最后的数字。先枚举出这个数 \(x\)，并将 \(a_i \ge x\) 的数设为 \(1\)，\(a_i < x\) 的数设为 \(0\)，然后做题目中的操作，若为 \(0\)，则最终结果小于 \(x\)，为 \(1\) 则大于等于 \(x\)。

使用二分可以优化到 \(\Omicron(n^2\log n)\)。

如果将每个位置扩展到整个序列，剩下的按照同样的做法，虽然无法进行二分优化，但复杂度降低到了 \(\Omicron(n^2)\)。

我们发现，\(01\) 序列的情况很特殊，如果将相邻两项相同的位置断开，也就是形成若干个内部都是 \(01\) 相间的段，每段都是一个与原序列相同的子问题，因为段的两端都不会改变。而且因为其内部的特殊性，可以轻松的计算出操作次数 \(\lfloor\frac{r -l}{2}\rfloor\)，以及最终的值。并且因为修改一个位置只会影响 \(\Omicron(1)\) 个段，所以这种段可以用 set 轻松维护。

每次修改之后都会导致出现新出现一些最终值从 \(0\) 变为 \(1\) 的区间，这些区间都在新出现的段中，所以我们可以在维护段的时候顺便统计答案。

复杂度 \(\Omicron(n\log n)\)。