CF1707E Replae | CmsBlog

描述

3500*。

乍一看没有什么很好的思路。观察一下 $f$ 的性质，将其换一个方式来表示，可以发现： $f((l,r)) = \cup_{i=l}^{r - 1}f((i, i + 1))$ 。这是显然的，这个集合是比他小的交起来得到。

然后，其实这相当于有结合律，很容易去拿各种奇怪高级数据结构去想办法维护。但是发现行不通。

考虑再看看有什么性质。我们要求的等价于最小的 $k$ 使得 $f^k((l,r))=(1,n)$ 。这样引发我们对 $f^k$ 进行探索。

再刚刚性质的启发下，我们手玩几组不难发现 $f^k((l,r)) = \cup_{i=l}^{r - 1}f^k((i, i + 1))$ 。

证明非常容易。假设 $(l,r) \cup (L,R) \neq \emptyset$ ，那么 $f((l,r)) \cup f((L,R)) \neq \emptyset$ 。依次归纳上去即可。

$k$ 可能很大，可以考虑想办法给他挂到 $\log$ 里。在指数上的话可以考虑倍增。

然后类似于 st 表一样维护 $f^{2^k}(x, x + 2 ^ t - 1)$ 的答案就可以了。

时间复杂度：假设 $q = \Theta(n)$ ，粗略实现 $\mathcal{O}(n \log^2 n)$ ，精细实现可以做到 $\mathcal{O}(n \log n)$

写的很丑啊。1500ms 的题目跑了 1496ms,喜提最劣解。