题解：CF1707E Replace

Tomwsc · 2026-11-11 10:46:22 · 题解

好牛的题。

考虑到直接做状态数是 n^2，非常困难。所以考虑一些观察，以将状态数简化。

这里是很厉害的一个想法，我们考察 f 的运算，尝试通过合并得到 f。

观察到 f([l, r])=\bigcup\limits_{i\in[l, r)}f([i, i+1])。证明是简单的。那么我们可以考虑倍增，观察 f^{k} 的变化，发现仍然满足上面的式子。这里证明归纳一下即可。我们可以先 ST 表预处理出 i 开头的长度为 2^k 的区间经过一次操作的结果，然后便对所有的 n\log n 个区间进行倍增，每次倍增转移都需要进行一次 RMQ。不过因为使用的是 ST 表，所以 RMQ 可以做到 \mathcal O(1)。

答案的查询也是简单的，直接倍增跳就做完了。

时间复杂度便是 \mathcal O(n\log^2 n+q\log n)。