矩形覆盖计数

形式化题目

给定 $N$ 个半开矩形 $[l_i,r_i)\times[d_i,u_i)$ 和 $M$ 个点 $(x_j,y_j)$ ，对每个点求出覆盖它的矩形个数。覆盖的定义是 $l_i \leqslant x_j < r_i$ 且 $d_i \leqslant y_j < u_i$ ——右、上边界不算覆盖。

$N,M \leqslant 10^5$ ，坐标 $\leqslant 10^9$ 。

暴力解法

思路

按定义做：每个询问点扫一遍所有矩形，四个不等式全部成立就 $+1$ 。

这既是最容易写对的版本，也是用来对拍的基线。它的瓶颈很明确—— $N$ 和 $M$ 都是 $10^5$ ， $NM = 10^{10}$ ，远超任何时限。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-17 22:52
 * update_at: 2026-10-17 22:52
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
// 直接按定义做：对每个询问点扫一遍所有矩形，判断 l <= x < r 且 d <= y < u，
// 命中的就 +1。复杂度 O(N * M)，只适合小数据（N、M 几百以内）。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int maxn = 100005;

int n, m;              // 矩形个数、询问个数
int rl[maxn], rd[maxn], rr_[maxn], ru[maxn]; // 第 i 个矩形 [l, r) x [d, u)
int qx[maxn], qy[maxn];                       // 第 j 个询问点 (x, y)

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> rl[i] >> rd[i] >> rr_[i] >> ru[i];
    for (int j = 1; j <= m; j++) cin >> qx[j] >> qy[j];

    for (int j = 1; j <= m; j++) {
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            // 半开区间：左、下边界含，右、上边界不含
            if (rl[i] <= qx[j] && qx[j] < rr_[i] && rd[i] <= qy[j] && qy[j] < ru[i]) cnt++;
        }
        printf("%d\n", cnt);
    }
    return 0;
}

复杂度

时间： $O(NM)$ ， $10^{10}$ 量级。
空间： $O(N+M)$ 。

瓶颈

「每个点都要重新看一遍所有矩形」这件事完全没必要：一个矩形只在一个 x 区间里有效，所以按 x 从小到大扫过去，它可以只在两个时刻改变状态——进入扫描线（ $x=l$ ）和离开扫描线（ $x=r$ ）。这才是本题真正的结构。

正解：扫描线 + 树状数组

关键观察

把「矩形是否覆盖当前扫描线」看成一份在 y 轴上的区间加记录：

扫描到 $x=l_i$ 时，y 区间 $[d_i,u_i)$ 上的覆盖数全部 $+1$ ；
扫描到 $x=r_i$ 时，这个区间全部 $-1$ 。

于是每个矩形变成两个事件，每个询问点变成「在它自己的 $x$ 处读一下 y 轴上的当前值」。

半开区间正好被这个顺序自动处理：同一个 $x$ 上先做矩形事件、再回答询问。这样 $x=l$ 的矩形已经加进来了（左边界算覆盖）， $x=r$ 的矩形已经减掉了（右边界不算覆盖），不需要任何特判。

y 方向的「区间加 + 单点查」用差分 + 树状数组：

区间 $[d,u)$ 加 $v$ $\iff$ 差分数组上 $d$ 处 $+v$ 、 $u$ 处 $-v$ ；
查 $y$ 处当前值 $\iff$ 差分数组前缀和到 $y$ 。

坐标到 $10^9$ ，先离线把所有 $d_i,u_i,y_j$ 收集起来离散化，树状数组只开 $O(N+M)$ 个位置。

思路

读入全部矩形与询问，把每个 $d_i$ 、 $u_i$ 、 $y_j$ 收进一张表做离散化。
建事件：每个矩形两个（ $x=l$ 加、 $x=r$ 减，都带离散化后的 y 区间），每个询问一个。
事件按 $(x,\text{kind})$ 排序， $\text{kind}$ 让矩形事件排在询问前面。
顺序扫描：矩形事件在差分数组上做两次单点加；询问事件取一次前缀和写进答案。

代码

C++ 版：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-17 22:52
 * update_at: 2026-10-17 22:52
 */
// main.cpp：静态「矩形覆盖计数」——扫描线 + 树状数组。
//
// 矩形是半开的 [l,r) x [d,u)。把「覆盖次数」沿 x 方向拆成两个事件：
//   x = l 处对 y 区间 [d,u) 加 1（矩形从这里进入扫描线）
//   x = r 处对 y 区间 [d,u) 减 1（矩形从这里离开扫描线）
// 所有事件按 x 升序扫描，同一 x 先做矩形事件再回答询问：
// 这样 x == l 的矩形已经加进来、x == r 的矩形已经减掉，恰好是半开区间。
//
// y 方向用「差分 + 树状数组」：区间加变成两次单点加，单点查变成一次前缀和，
// 每个事件只要 O(log) 时间，总复杂度 O((N + M) log (N + M))。

#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 100005;
const int MAXE = 3 * MAXN; // 事件上限：2N 个矩形事件 + M 个询问（N、M <= 1e5）

// 一个事件要么是矩形在 x 处的进出，要么是一个询问点
struct Event {
    int x;      // 事件发生的 x 坐标
    int kind;   // 0 = 矩形事件，1 = 询问
    int sign;   // 矩形事件：+1 表示在 x 处进入，-1 表示在 x 处离开
    int lo;     // 矩形事件的 y 区间下界（已离散化，闭）
    int hi;     // 矩形事件的 y 区间上界（已离散化，开）
    int y;      // 询问点的 y（已离散化）
    int id;     // 询问编号，按输入顺序输出
};

Event ev[MAXE]; // 所有事件，最后按 x 升序扫描
int ev_cnt;     // 事件个数

int ys[MAXE];  // 离散化用的 y 坐标：矩形的上下边界 + 询问点的 y
int ys_cnt;    // 去重后的 y 个数，也是树状数组长度
int ans[MAXN]; // ans[j]：第 j 个询问的覆盖矩形个数
int bit[MAXE]; // 树状数组：维护 y 方向差分数组，区间加两次单点加即可

// 登记一个矩形事件：在 x 处把 y 区间 [lo, hi) 加上 sign
void add_rect_event(int x, int sign, int lo, int hi) {
    ev_cnt++;
    ev[ev_cnt].x = x;
    ev[ev_cnt].kind = 0;
    ev[ev_cnt].sign = sign;
    ev[ev_cnt].lo = lo;
    ev[ev_cnt].hi = hi;
    ev[ev_cnt].y = 0;
    ev[ev_cnt].id = 0;
}

// 登记一个询问事件：在 x 处查询点 (x, y)
void add_query_event(int x, int y, int id) {
    ev_cnt++;
    ev[ev_cnt].x = x;
    ev[ev_cnt].kind = 1;
    ev[ev_cnt].sign = 0;
    ev[ev_cnt].lo = 0;
    ev[ev_cnt].hi = 0;
    ev[ev_cnt].y = y;
    ev[ev_cnt].id = id;
}

// 事件排序：x 升序；x 相同则矩形事件（kind = 0）排在询问前面
bool cmp_event(Event a, Event b) {
    if (a.x != b.x) return a.x < b.x;
    return a.kind < b.kind;
}

// 树状数组：单点加
void bit_add(int i, int v) {
    for (; i <= ys_cnt; i += i & -i) bit[i] += v;
}

// 树状数组：前缀和，即 y 方向差分数组前 i 项之和 = 第 i 个 y 坐标处的覆盖次数
int bit_sum(int i) {
    int s = 0;
    for (; i > 0; i -= i & -i) s += bit[i];
    return s;
}

// 在离散化数组 ys[1..ys_cnt] 中找第一个 >= v 的位置（1 下标）
int lower_id(int v) {
    return lower_bound(ys + 1, ys + ys_cnt + 1, v) - ys;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    // 先把矩形和询问读进来：y 坐标要整体离散化，必须先读完才知道有哪些值
    int rl[MAXN], rd[MAXN], rr[MAXN], ru[MAXN]; // 第 i 个矩形的 l、d、r、u
    for (int i = 1; i <= n; i++) {
        scanf("%d %d %d %d", &rl[i], &rd[i], &rr[i], &ru[i]);
        ys[++ys_cnt] = rd[i];
        ys[++ys_cnt] = ru[i];
    }
    int qx[MAXN], qy[MAXN];
    for (int j = 1; j <= m; j++) {
        scanf("%d %d", &qx[j], &qy[j]);
        ys[++ys_cnt] = qy[j];
    }

    // y 离散化：排序去重
    sort(ys + 1, ys + ys_cnt + 1);
    ys_cnt = unique(ys + 1, ys + ys_cnt + 1) - (ys + 1);

    // 建事件：每个矩形拆成「进」「出」两个，每个询问一个
    for (int i = 1; i <= n; i++) {
        int lo = lower_id(rd[i]); // d 的位置：覆盖判定从这里开始
        int hi = lower_id(ru[i]); // u 的位置：覆盖判定到这里结束（开）
        add_rect_event(rl[i], +1, lo, hi);
        add_rect_event(rr[i], -1, lo, hi);
    }
    for (int j = 1; j <= m; j++) add_query_event(qx[j], lower_id(qy[j]), j);

    // 扫描线：按 x 从小到大处理所有事件
    sort(ev + 1, ev + ev_cnt + 1, cmp_event);
    for (int i = 1; i <= ev_cnt; i++) {
        if (ev[i].kind == 0) {
            // 区间加 [lo, hi)：差分上就是 lo 处加、hi 处减
            bit_add(ev[i].lo, ev[i].sign);
            bit_add(ev[i].hi, -ev[i].sign);
        } else {
            // 单点查：前缀和就是 y 处当前被多少个矩形覆盖
            ans[ev[i].id] = bit_sum(ev[i].y);
        }
    }

    for (int j = 1; j <= m; j++) printf("%d\n", ans[j]);
    return 0;
}

Python 版（同一算法，事件用元组直接排序）：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-17 22:52
# update_at: 2026-10-17 22:58
#
# 静态矩形覆盖计数：扫描线 + 树状数组（rbook_nunjucks 代码模板风格）。
# 矩形是半开的 [l, r) x [d, u)。按 x 扫描：
#   x = l 处对 y 区间 [d, u) 加 1（矩形进入扫描线）
#   x = r 处对 y 区间 [d, u) 减 1（矩形离开扫描线）
# 同一 x 先做矩形事件、再回答询问，于是 x == l 已算覆盖、x == r 已不算覆盖。
# y 方向用「差分 + 树状数组」，区间加变两次单点加，单点查变一次前缀和。
# 坐标全部 1 下标（离散化后的名次也从 1 开始）：lowbit(0) = 0 会让修改循环原地打转。

import sys

type Seq = list[int]  # 1 下标 int 序列，下标 0 占位不用


def solve() -> None:
    data = list(map(int, sys.stdin.buffer.read().split()))
    pos = 0

    n = data[pos]
    m = data[pos + 1]
    pos += 2

    # 矩形 (l, d, r, u)；同时收集 y 方向要离散化的坐标
    rects: list[tuple[int, int, int, int]] = []
    ys: Seq = [0]  # 下标 0 占位
    for _ in range(n):
        l, d, r, u = data[pos], data[pos + 1], data[pos + 2], data[pos + 3]
        pos += 4
        rects.append((l, d, r, u))
        ys.append(d)
        ys.append(u)

    # 询问点 (x, y)
    queries: list[tuple[int, int]] = []
    for _ in range(m):
        x, y = data[pos], data[pos + 1]
        pos += 2
        queries.append((x, y))
        ys.append(y)

    # y 离散化：值 -> 1 起的名次
    ordered = sorted(set(ys[1:]))
    rank = {v: i for i, v in enumerate(ordered, start=1)}
    ys_cnt = len(ordered)

    # 事件统一成 7 元组，直接靠元组比较排序：
    #   (x, kind, sign, lo, hi, y, id)
    #   kind = 0 矩形事件：sign = ±1，影响离散化区间 [lo, hi)
    #   kind = 1 询问事件：查离散化名次为 y 的位置，编号 id
    # kind 放在第二关键字，保证同一 x 上矩形事件先于询问事件。
    events: list[tuple[int, int, int, int, int, int, int]] = []
    for l, d, r, u in rects:
        lo = rank[d]
        hi = rank[u]
        events.append((l, 0, 1, lo, hi, 0, 0))   # 从 l 开始覆盖
        events.append((r, 0, -1, lo, hi, 0, 0))  # 到 r 就不覆盖了
    for j, (x, y) in enumerate(queries):
        events.append((x, 1, 0, 0, 0, rank[y], j))
    events.sort()

    tree: Seq = [0] * (ys_cnt + 1)  # 树状数组维护 y 方向的差分数组
    answer: Seq = [0] * m

    for x, kind, sign, lo, hi, y, idx in events:
        if kind == 0:
            # 差分：区间 [lo, hi) 加 sign = lo 处 +sign、hi 处 -sign
            i = lo
            while i <= ys_cnt:
                tree[i] += sign
                i += i & -i
            i = hi
            while i <= ys_cnt:
                tree[i] -= sign
                i += i & -i
        else:
            # 差分前缀和 = 该 y 处当前被多少个矩形覆盖
            total = 0
            i = y
            while i > 0:
                total += tree[i]
                i -= i & -i
            answer[idx] = total

    sys.stdout.write("\n".join(map(str, answer)) + "\n")


if __name__ == "__main__":
    solve()

复杂度

时间： $O((N+M)\log(N+M))$ ，每个事件一次树状数组操作。
空间： $O(N+M)$ 。

实测：C++ 16 个数据点全部 AC，最慢 144 ms / 14 MiB；Python 全部 AC，最慢约 1.8 s / 119 MiB。

总结

「矩形覆盖点」的通用套路是扫描线去掉一维、数据结构维护另一维。这里去掉的是 x，维护的是 y。
半开区间 $[l,r)$ 不需要额外判断：把「进入事件」和「离开事件」分别放在 $x=l$ 、 $x=r$ ，并规定同 $x$ 先处理事件、后回答询问，边界语义就自然正确了。这条规则是本题最容易写错的地方。
y 方向用「差分 + 树状数组」实现区间加、单点查，比线段树短得多；坐标大时必须先离散化。
本题是静态版本。如果把「加矩形」也变成在线操作，x 就不能提前扫完了——那就需要把这里的「一维差分 + 前缀和」升到二维，见 roj-1415 矩形加点求和。

目录

形式化题目

暴力解法

思路

代码

复杂度

瓶颈

正解：扫描线 + 树状数组

关键观察

思路

代码

复杂度

总结