5
树上莫队和树上分块
source link: https://rapiz.me/2017/motao-shang-shu/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
树上莫队和树上分块
带修改莫队
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})$
ProbHintBZOJ2120 数颜色这题有很麻烦的分块做法。带修改莫队简单不少
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK