题解 P6783 【[Ynoi2008]rrusq】

· · 题解

我来复读一遍lxl题解(

首先离线询问，从小到大扫描右端点，考虑维护每个点在当前扫描线过程中包含它的矩形中最靠右的 r_i，那么查询的时候只需要计算满足 r_i\geq l 的点 i 的点权和.

考虑新加入一个矩形 x，它的影响是把所有在这个矩形内的点的 r_i 更新为 x. 使用 KDTree 来完成这个矩形覆盖操作，再用另一个数据结构对每个 k 维护满足 r_i=k 的点权和. 当一个 KDTree 节点的矩形完全被操作矩形包含时，首先回收它子树内的所有标记，然后在这个节点打上标记，同时对应地在另一个数据结构上做修改. 回收标记的复杂度显然可以被均摊掉（一放一收），所以 KDTree 部分会有 O(n\sqrt{n}) 次单点加，还有 q 次查询后缀和，可以使用 O(1)-O(n^{\epsilon}) 的分块，但因为 KDTree 跑得太太太太太慢了所以直接用 O(1)-O(\sqrt{n}) 的分块即可（这部分的时间比起 KDTree 部分小得多）.

看题解长度好像也不是很难

关于这个 O(1)-O(n^{\epsilon}) 的分块好像还是有挺多人不知道的，所以来说一下. 考虑常规的分块其实是一个 \sqrt n 叉树，我们可以把这个 \sqrt{n} 替换成别的东西，比如说 n^{1/3}，我们可以用树高的代价完成修改，用树高乘叉数完成查询（或者交换查询和修改）. 一般来说，如果用 x 叉树，那么树高为 h(n)=h(n/x)+1=O(\dfrac{\log n}{\log x})，可以做到 O\left(\dfrac{\log n}{\log x}\right)-O\left(\dfrac{x\log n}{\log x}\right) 或者两边反过来，可以用来平衡一些奇怪的问题（比如有 n\log n 次区间和以及 O(n) 次单点修改，这时会平衡为 O(n\log^2n/\log\log n)）

代码不放了 反正很好写(