树上莫队

转dfs序的写法
直接上

带修改莫队

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$ 使总复杂度最小,于是令
$$N^3/T^2 = NT$$
即解得
$$T = N^{2/3}$$
回代得算法总复杂度为$O(N^{5/3})$

Prob Hint
BZOJ2120 数颜色 这题有很麻烦的分块做法。带修改莫队简单不少