自动搬运

查看原文

来自洛谷，原作者为

	hhoppitree 成功的秘诀只有一个：加训。故古语有云：日拱一卒，功不唐捐；玉汝于成，溪达四海。

搬运于2025-08-24 23:09:32，当前版本为作者最后更新于2025-02-09 12:24:06，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

考虑求补集的并集的补集，也就是，离线扫描线，一开始每个点有一个颜色，每次修改将半平面的补的颜色改为 $i$，查询颜色为 $[0,l)$ 的集合的点的信息和。

如果数据随机，可以考虑建立一棵 Leafy 的二叉 KD-Tree，则每次相当于将 $\mathcal{O}(\log n)$ 个区间重染色，我们暴力递归将这棵子树划分成若干棵小子树，其中每个子树内的点颜色相同，这样修改量的总和是 $\mathcal{O}(m\log n)$ 的，而前缀信息和询问量是 $\mathcal{O}(q)$ 的，分块即可。

如果不随机，考虑用平面上的 Optimal Partition Tree，每次在分裂和合并的时候上传标记即可，由于上文提到的“递归处理”方式所以一个点上和子树内不可能同时有标记，这样修改的次数是 $\mathcal{O}(n+m\sqrt{n})$ 的，总操作次数为 $\mathcal{O}(n+m\sqrt{n}+q\sqrt{m})$，时间复杂度容易做到 $\tilde{\mathcal{O}}(n+m\sqrt{n}+q\sqrt{m})$。