描述

题目传送门

思路

3500*。

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

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

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

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

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

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

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

时间复杂度:假设 q=Θ(n)q = \Theta(n), 粗略实现 O(nlog2n)\mathcal{O}(n \log^2 n),精细实现可以做到 O(nlogn)\mathcal{O}(n \log n)

代码

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

Link\mathcal{Link}