离线二维数点

whisper_free_Evil · 2026-06-14 10:27:47 · 算法·理论

离线二维数点

概念

给定一些点，求平面内一些长方形内点的数量。

经典题型

1. 给定平面上 n 个点，q 次询问一个矩形内有多少个点（或点权和）。把询问拆成前缀相减，离线后从左到右扫，用 DS 维护 y 轴。

2. 给定平面上 n 个点，找一个固定大小 h \times w 的矩形，使得矩形内点数（或点权和）最优。

   • 滑动窗口理解：枚举左右边界，窗口从左到右滑动，不断加点删点。每个点 (x_i, y_i) 会对一段 y 区间 [y_i, y_i + h) 产生贡献，用 DS 维护区间修改和全局最值。

   • 差分理解：每个点产生两条差分线，离线后用 DS 处理区间修改和全局最值。

   两种理解最终代码基本相同。

算法思想

二维数点的核心就一件事：把二维问题变成一维。怎么变？类似二维偏序，先把询问离线，按一维排序后扫过去，另一维用 DS 维护。扫的时候加点删点查询即可，DS 里永远只能有当前扫描线覆盖到的点。至于使用哪种 DS，看询问需要什么就好了。

例题

luoguP10814 【模板】离线二维数点

题意

给定一个长度为 n 的序列 a，给定 m 次询问，求区间 [l, r] 里 \le x 的个数。

思路

题目查询的限制是

如果转换为二维数点，那么其实这个长方形的左下角就是 (l, 0)，右上角就是 r, x（这里 x, y 坐标反过来也可以）。

所以我们就可以建点 (i, a_i)，然后做二维数点。

这个似乎很像二维偏序？那么我们就可以按 x 从小到大扫（也就是消掉 x 的限制），扫到一个询问时，所有符合 \le x 的点都已经加进去了，DS 里正好就是满足条件的点，答案就是 DS 的 query(r) - query(l - 1)。这样就把二维问题降成了一维，然后加点就是在 i 位置 +1，表示这个位置有一个满足 \le x 的点。查询 [l, r] 就是看这个区间里有多少个这样的点。

时空复杂度

时间复杂度：O((n + m) \log n)。

空间复杂度：O(n + m)。

AT_abc327_f Apples

题意

给定 n 个苹果，第 i 个在时间 t_i 掉在坐标 x_i。再给定一个篮子，长度是 w，能用 d 单位时间。你可以选一个开始时间 s 和一个左端点 l，篮子会盖住 [l, l + w) 这块地方在时间 [s, s + d) 掉落的苹果。问最多能拿几个苹果。

思路

篮子有两个窗口：时间上 [s, s + d)，空间上 [l, l + w)。一个苹果 (t_i, x_i) 要被接住，必须同时满足：

第二个条件可以转换为左端点 l 的范围：

也就是说每个苹果会对一段连续的左端点区间产生贡献。

那么我们有了这个公式就可以先按照 x 坐标排序（也就是时间维），然后从小到大扫。篮子长度固定，那么苹果就会在当前 x = t_i 的时间加入，在 x = t_i + d 时删除，那么就用 DS 维护。

然后由于苹果是对左端点区间产生贡献，所以我们可以把每个区间都看成一个带权的点（左端点 l），然后答案就是 DS 里的全局最大值。

时空复杂度

时间复杂度：O((n + V) \log V)，V 是坐标范围。

空间复杂度：O(n + V)。

luoguP2163 园丁的烦恼

题意

给定 n 个点，求 m 个矩形分别覆盖了多少个点。

思路

很明显的二维数点模板题。按照二维前缀和的思想把矩形拆成四个前缀查询即可。然后唯一的坑点就是坐标需要离散化。

时空复杂度

时间复杂度：O((n + m) \log (n + m))。

空间复杂度：O(n + m)。

luoguP8844 小卡与落叶

题意

有一棵 n 个点根为 1 的树，有 m 次操作。每次可以染色（深度 \ge d 的点染黄）或查询（子树 u 中有多少黄点）。

思路

树上问题可以先转成序列，一棵子树的 DFS 序一定是连续的。设 l_u, r_u 为子树中 DFS 序位置的最小值（就是 u 的 DFS 序位置）和最大值，设 d 就是上一次染色操作的深度，那么查询操作就变成了有多少点 v 满足

然后要把它转换为二维数点公式那就可以变成

所以我们可以把 DFS 序当 x 轴，深度当作 y 轴。而查询则是先离线下来再二维数点算答案即可。

时空复杂度

时间复杂度：O((n + m) \log n)。

空间复杂度：O(n + m)。