自动搬运

查看原文

来自洛谷，原作者为

	qwaszx 不再为往事受困.

搬运于2025-08-24 22:23:55，当前版本为作者最后更新于2020-10-07 09:56:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我来复读一遍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)$）

代码不放了 反正很好写(