NOIP 前的复习乱写

莫队

询问是二维的莫队

把询问抽象成平面上的点 \((x,y)\)，那么处理两个询问间的指针移动就是两点之间的曼哈顿距离。

我们需要构造一个处理点的顺序来使得指针移动和尽量小。

将 \(x\) 轴按照 \(O(B)\) 块长分为 \(O(\frac{n}{B})\) 块，将点按照 \(x\) 所在块编号升序排序，同一块内按照 \(y\) 升序排序。

我们把点在 \(x\) 轴和 \(y\) 轴上的移动分开考虑：

对于 \(x\)，在同一块内一次移动 \(O(B)\)，共有 \(O(q)\) 次，跨块的移动只有 \(O(\frac{n}{B})\) 次，每次也是 \(O(B)\) 的，总移动 \(O(qB+n)\)。

对于 \(y\)，在同一块内移动 \(O(n)\)，共有 \(O(\frac{n}{B})\) 块，在跨块的时候移动回去也是 \(O(n)\) 的，共有 \(O(\frac{n}{B})\) 次，总移动 \(O(\frac{n^2}{B})\)。

设指针移动一单位的代价是 \(f_0\)，查询代价是 \(f_1\)，总时间复杂度 \(O((qB+\frac{n^2}{B})f_0+qf_1)\)。

取 \(B=O(\frac{n}{\sqrt{q}})\) 得到最优复杂度 \(O(n\sqrt{q}f_0+qf_1)\)。

注意到指针移动是 \(O(n\sqrt{q})\) 的而查询只有 \(O(q)\) 次，如果 \(f_0,f_1\) 代价不为 \(O(1)\)，我们可以考虑根号平衡。

• P4396 [AHOI2013]作业

考虑如何维护莫队元素集合，如果使用树状数组那么 \(f_0=f_1=O(\log n)\)，总时间复杂度 \(O(n\sqrt q\log n)\)。

利用上面的原理，考虑使用 \(O(1)\) 单点加 \(O(\sqrt n)\) 区间求和的分块来平衡复杂度，总时间复杂度 \(O(n\sqrt q+q\sqrt n)\)。

其它普通莫队的难点就在于如何维护莫队元素集合。

询问是三维的莫队

把询问抽象成三维的点 \((x,y,z)\)，类似二维莫队。

对 \(x\) 和 \(y\) 轴都分块，将点按照 \(x\) 轴所在块编号升序排序，同一 \(x\) 轴块内的点再按照 \(y\) 轴所在块编号升序排序，最后在同一 \(x,y\) 轴块内的点再按照 \(z\) 升序排序。