总结：一种可重复贡献的修改问题

· · 算法·理论

声明：以下的 k 未说明时都是区间长度的以 2 为底的对数下取整。

考虑一个问题：给定长度为 n 的序列 a，有 m 次区间取 \max 操作，要求输出操作完后的序列。其中 1\le n\le 10^5,1\le m\le 2\times10^7。

一般的做法就是用一棵线段树直接修改。这样的复杂度是 O(n+m\log{n})。由于 m 过大，这显然不可行。

事实上，作者在模拟赛上用分块成功做到了 O(n^{\frac{4}{3}}+m) 的复杂度，但是还有更优的做法。

考虑到一个显然的事实：将一个数对 v 取多次 \max 和取一次是一样的，不会改变结果。

注意到普通 ST 表的复杂度是 O(n\log{n}) 预处理，O(1) 查询。那么我们能否把 ST 表反着写，做到 O(1) 修改，O(n\log{n}) 查询呢？

是可行的。考虑直接在 ST 表上面打标记，令 f_{i,j} 表示序列上区间 [i,i+2^j-1] 的取 \max 标记。那么对于一次将 [l,r] 对 v 取 \max 的操作，只要更新 f_{l,k} 和 f_{r-2^k+1,k} 即可。

修改完后，可以依次把标记从 f_{i,j} 下传到 f_{i,j-1} 和 f_{i+2^{j-1},j-1}。最后的 f_{i,0} 即为答案。

这种做法的正确性需要保证修改运算是可重复贡献的。例如 \gcd,\min,\max 等。

推而广之，实际上也不一定是运算。看这个题：

有一个长度为 n 的序列 a，每个值都未知。有 m 个限制，每个都形如两个等长度区间 [l_1,r_1] 和 [l_2,r_2] 对应位置的值相等。求这个序列中的数最多有几种值。

原题：P12736 [POI 2016 R2] 圣诞灯链

一种暴力的做法很显然：维护一个并查集，两个数在一个联通块里意味着两个位置的值一定相等。对每个限制，把对应位置合并，答案就是最后的联通块数。

依然可以发现，合并操作在某种意义上是可重复贡献的。考虑用 f_{i,j} 表示 [i,i+2^j-1] 这段区间。那么一个限制 [l_1,r_1],[l_2,r_2] 只要把 f_{l_1,k} 和 f_{l_2,k} 合并，把 f_{r_1-2^k+1,k} 和 f_{r_2-2^k+1,k} 合并即可。注意到修改都是在同一个 k 上进行的。

最后下传标记时，把在同一个集合里的 f_{i,k},f_{j,k} 对应的左半区间和右半区间分别合并即可。

类似题：P3295 [SCOI2016] 萌萌哒

为什么这种做法会更快呢？实际上是因为 ST 表相比线段树把区间拆得更少，可以拆成两个重叠的区间。所以在可重复贡献时 ST 表的优势很大。

劣势就在于这个做法不能在线，必须修改完才能输出。

顺便提一嘴，如果不可重复贡献分块也是可以做到 O(n^{\frac{4}{3}}+m) 的。

感谢 tdog 张开元老师对我的启发。