Codeforces Round 808 E

feecle6418 · 2022-07-18 22:24:23 · 题解

注意到 f(l,r)=\cup_{i=l}^{r-1} f(i,i+1)。

这个观察本身就很有启发意义，因为相当于告诉我们对于这种看上去没啥性质的函数应该观察其结构，找到一些结构上的性质，使得我们能用某种结构去维护它。

考虑把上面的结论推广，我们断言 f^k(l,r)=\cup_{i=l}^{r-1} f^k(i,i+1)。

证明：

• 先证明引理：若 [l,r],[L,R] 有交，则 f(l,r),f(L,R) 有交（这显然）。进一步有 f^k(l,r),f^k(L,R) 有交。
• 接着证明若 [l,r],[L,R] 有交，则 f(l,r)\cup f(L,R)=f(\min(l,L),\max(r,R))，这也是显然的。因此证毕。

有了上面的结论后，问题变得很简单：倍增预处理 f^{2^k}(i,i+1)（每次倍增都需要 rmq），查询时也倍增即可。复杂度 O(n\log^2 n+q\log n)（当然可以优化到 O(n\log n+q\log n)）。