浅谈二维数颜色问题的各种解法

最近 ZR 出了一次，学长的讲课也讲了一次，于是想开一篇博客记录的各种解法。 > 有一个 $n\times m$ 的平面，其中有 $k$ 个点 $(a_i,b_i)$。有 $q$ 次询问，每次给定一个矩形，询问满足 $x_1\le a\le x_2,y_1\le b\le y_2$ 不同的 $a/b$ 的个数。数据保证没有重复的点。 此处认为 $n$ 和 $m$ 同阶，且 $n,m\le k$。 注意到求不同的 $a/b$ 的个数是等价的，所以下面的讨论是求不同的 $b$ 的个数。 ### 解法 $1:\text{CDQ}$ 分治 二维数颜色的问题是一维数颜色拓展版本，考虑三维数点。定义 $pre_i$ 为将点按 $a$ 排序后，$j<i,b_i=b_j$ 最大的 $x_j$。这样只用数 $x_1\le i\le x_2,pre_i<x_1,y_1\le b\le y_2$ 的个数，时间 $\mathcal{O}((q+k)\log k\log n)$。但是 $\text{CDQ}$ 分治需要拆 $4$ 次询问，效率和根号算法差不多。 ### 解法 $2:$ 莫队+分块 类似小清新人渣的本愿，用莫队维护每个数的出现次数，然后采用 $\mathcal{O}(1)-\mathcal{O}(\sqrt{n})$ 的分块，时间 $\mathcal{O}(k\sqrt{q}+q\sqrt{n})$。这种做法常数小，也好写，在离线算法中是很优秀的。 那么问题来了：怎么做在线版本呢？ ### 解法 $1:$ 树套树 你确定时间和空间都跑得过？ ### 解法 $2:$ 线段树 $+\ \text{bitset}$ 建一棵线段树，在每个结点上维护一个 $\text{bitset}$。因为这个 $\text{bitset}$ 中只有 $\mathcal{O}(k\log n)$ 个 $1$，可以手写 $\text{bitset}$。空间十分优秀，但是时间 $\mathcal{O}(\frac {qk\log n}{w})$，其中 $w=32/64$。我觉得可能循环展开的暴力可能和这个做法的实际效率差不多。 ### 解法 $3:$ 分块 $+\ \text{bitset}$ 我们考虑维护两个块之间 $\text{bitset}$，然后边角暴力。若块长为 $B$，那么时间 $\mathcal{O}(\frac {k^2n}{B^2w}+qB)$，空间 $\mathcal{O}(\frac {k^2n}{B^2w})$，其中 $w=32/64$。在实际实现中 $B$ 要取到 $\frac {k}{200}$ 左右，时间和空间都不尽人意。 ### 解法 $4:$ 优化解法 $3$ 的常数 我们发现处理两个块之间的 $\text{bitset}$ 很慢，考虑猫树的结构，在猫树上分块，类似根号树。 令 $B=\sqrt k$，这样的话我们只用存 $\sqrt{k}\log n$ 个 $\text{bitset}$，时间 $\mathcal{O}(\frac {k\sqrt k\log n}{w}+q\sqrt{k}+\frac {qn}{w})$，空间 $\mathcal{O}(\frac {k\sqrt k\log n}{w})$，其中 $w=32/64$。这样时间和空间都能降下来，算法瓶颈在 $\frac {qn}{w}$ 上。因此这种做法在 $n$ 较小的时候时间和空间都十分优秀。