树上莫队
带修改莫队
mzx: 分 $n^{1/3}$ 块, 按左右端点所在块、修改时间为关键字排序。
mzx: 想象平面上两个轴被割开,于是平面被割为正方形。
算法过程:排序、暴力回滚/前进修改
为什么是$\frac{1}{3}$?
下证复杂度。
假设读者掌握了普通莫队复杂度的证明。
我们把左右端点看成 x,y 轴,按$T$划分。此时平面被分为$T\times T$的正方形。每个正方形是现在的一块,其边长为$T$,面积为$T^2$。
可以说是先按一个轴分块之后再按另一个轴分块,也可以说是二维的分块。
每个块内的操作按时间排序。
靠北啊下面写错了好多次好丢人
考虑修改:
块内共$N$,共$(N/T)^2$块,总复杂度$N^3/T^2$。
跨块单次$N$,共$(N/T)^2$块,总复杂度$N^3/T^2$。
考虑端点:
每次$T$,复杂度$NT$。
我们要找到合适的 $T$ 使总复杂度最小,于是令
即解得
回代得算法总复杂度为$O(N^{5/3})$
Prob | Hint |
---|---|
BZOJ2120 数颜色 | 这题有很麻烦的分块做法。带修改莫队简单不少 |