树上莫队
带修改莫队
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 数颜色 | 这题有很麻烦的分块做法。带修改莫队简单不少 |