usaco-5.5.1 矩形周长

形式化题目

给定平面上 $N$ 个边平行于坐标轴的矩形，第 $i$ 个由左下角 $(x_{1i}, y_{1i})$ 和右上角 $(x_{2i}, y_{2i})$ 给出，且 $x_{1i} < x_{2i}$ 、 $y_{1i} < y_{2i}$ （面积为正）。矩形之间可以任意重叠，也可以完全包含。

设 $U = \bigcup_{i=1}^{N} [x_{1i}, x_{2i}] \times [y_{1i}, y_{2i}]$ 是这 $N$ 个矩形的并集。求 $U$ 的边界总长度：落在 $U$ 内部（两侧都被覆盖）的线段一律不计。

坐标均为 $[-10000, 10000]$ 内的整数；数据中 $N$ 最大约 $5 \times 10^3$ 。答案可能需要 32 位有符号整数表示。

以样例的 7 个矩形为例，把 $x$ 、 $y$ 上出现过的坐标收集起来切成条带，每个格子整体「被覆盖」或「整体空」：

text

1
2
3
4
5
6
7
8
9
10
11
12
13           -15 -5  0  2  5 10 15 16 20 24 30 34 36   <- x 条带左端点
[  22,  25)  .  #  #  #  #  #  #  #  .  .  .  .  .
[  20,  22)  .  #  #  #  #  #  #  #  .  .  .  .  .
[  16,  20)  .  #  #  #  #  #  #  #  .  .  #  #  .
[  15,  16)  .  #  #  #  #  #  #  #  .  .  #  #  #
[  14,  15)  .  #  #  #  #  #  #  #  .  .  #  #  #
[  10,  14)  .  #  #  #  #  #  #  #  #  .  #  #  #
[   8,  10)  #  #  #  #  #  #  #  #  #  .  .  #  #
[   4,   8)  #  #  #  #  .  .  #  #  #  .  .  #  #
[   0,   4)  #  #  #  #  #  #  #  #  #  .  .  #  #
[  -4,   0)  .  .  #  #  #  #  #  #  #  .  .  .  .
[  -6,  -4)  .  .  #  #  #  #  #  .  .  .  .  .  .
 y=25 以上                                       （全部为空）

# 表示该格子被至少一个矩形盖住。这张图只有 $11 \times 13$ 个格子，却完整保留了轮廓信息——这就是本题的突破口：坐标的取值只有 $2N$ 个是「有用」的，其余整数坐标都夹在中间陪跑。

正解

思路

朴素做法为什么不行为。 最直接的想法是把平面离散成整数单位格（坐标都是整数，一个矩形覆盖的正好是 $[x_1, x_2) \times [y_1, y_2)$ 内的单位格），涂完色再遍历每个格子，对每面与空格相邻的墙累加长度 $1$ 。

问题在于坐标值域。 $x$ 从 $-10000$ 到 $10000$ 共 $20001$ 种取值，于是网格有 $20001^2 \approx 4\times 10^8$ 个格子：即便每格只占 1 字节也要 400 MB，远超 128 MB；涂色与统计也都是 $4 \times 10^8$ 次操作。真正的原因不是「统计方法不好」，而是把整整 $20001$ 个坐标都当成了独立状态。

观察 1：只有矩形的边会切开状态。 把所有 $x_1, x_2$ 收集起来排序去重，得到 $x_{(1)} < x_{(2)} < \dots < x_{(k_x)}$ ，其中 $k_x \leqslant 2N$ 。

引理（条带内状态一致）：任取开条带 $(x_{(j)}, x_{(j+1)})$ 内两点 $a < b$ 。若某矩形覆盖 $a$ 却不覆盖 $b$ ，它必然有一条竖直边落在 $[a, b]$ 内，也就是某个 $x_1$ 或 $x_2$ 严格落在 $(x_{(j)}, x_{(j+1)})$ 内，与「相邻去重值之间没有其它坐标」矛盾。

因此每条开条带内每一点的覆盖状态完全相同；对 $y$ 方向同理。

于是平面被切成至多 $(2N-1)^2$ 个格子，每个格子整体被覆盖或整体为空。把条带宽度记作 $dx_j$ 、区间高度记作 $dy_i$ ，压缩过程不丢任何信息。

观察 2：轮廓长度 = 覆盖状态发生翻转的总量。 一段边界恰好出现在「被覆盖格子」与「相邻未覆盖格子」之间。所以：

水平边：某个 $x$ 条带在相邻两个 $y$ 区间上状态不同（一空一满），长度就是 $dx_j$ ；
竖直边：某个 $y$ 区间内部相邻两条 $x$ 条带状态不同，长度就是 $dy_i$ 。

这里不需要任何几何上的分类讨论：只要把「本行的覆盖状态」和「上一行的覆盖状态」逐条带比一遍，不同的位置正好就是水平边。

观察 3：竖直边可以顺手数出来。 在固定的 $y$ 区间里，把各 $x$ 条带的覆盖情况写成一个布尔序列 cover，想象在最左、最右两侧各接一个「空」条带。那么这段区间露出的竖直边条数是：

\text{border} = \texttt{cover}[0] + \texttt{cover}[-1] + \#\{j : \texttt{cover}[j] \neq \texttt{cover}[j-1]\}

前两项处理左右两端，第三项数内部跳变。乘上区间高度 $dy_i$ 就是该区间的竖直轮廓长度。

观察 4：不需要真的把矩阵存下来，扫一行就够。 压缩后最多有 $(2N-1)^2 \approx 10^8$ 个格子，显式建矩阵仍然会 MLE。关键是把每个矩形拆成 4 个事件：

事件	含义
$(Y,\ X,\ +1)$	从 $y$ 区间 $Y$ 开始，条带 $X$ 起被覆盖
$(Y,\ X_2,\ -1)$	从 $y$ 区间 $Y$ 开始，条带 $X_2$ 起不再被覆盖
$(Y_2,\ X,\ -1)$	从 $y$ 区间 $Y_2$ 开始撤销上面的 $+1$
$(Y_2,\ X_2,\ +1)$	从 $y$ 区间 $Y_2$ 开始撤销上面的 $-1$

自下而上扫 $y$ 区间，维护一个长度 $k_x$ 的 x 方向差分数组 level：把落在当前区间的事件累加上去，np.cumsum(level[:k_x-1]) > 0 就是本区间的 cover（差分数组故意留最后一格来接「最右端之后的 $-1$ 」，前缀和只读前 $k_x - 1$ 项）。整个过程只需要 $O(k_x)$ 的内存，等于把二维矩阵按行「流式」处理掉了。

有一个坑必须避开：同一行同一位置上可能同时有多个事件（例如两个矩形共享同一条竖直边），此时 level[pos] += inc 这种 fancy indexing 赋值只会保留最后一个，必须用 np.add.at 做真正的累加。

把样例跑一遍。 下表每行是一个 $y$ 区间：覆盖状态 按 $x$ 条带从左到右写（# 满、. 空），水平边 是与上一行比较后状态不同的条带长度和，竖直边 是 border × dy[i]，累计 是答案的推进过程。第一行之下没有矩形，因此 prev 全空。

$y$ 区间	覆盖状态（按 $x$ 条带）	水平边	竖直边	累计
$[-6, -4)$	`..#####......`	16	4	20
$[-4, 0)$	`..#######....`	8	8	36
$[0, 4)$	`#########..##`	21	16	73
$[4, 8)$	`####..###..##`	10	24	107
$[8, 10)$	`#########..##`	10	8	125
$[10, 14)$	`.########.###`	14	16	155
$[14, 15)$	`.#######..###`	4	4	163
$[15, 16)$	`.#######..###`	0	4	167
$[16, 20)$	`.#######..##.`	4	16	187
$[20, 22)$	`.#######.....`	6	4	197
$[22, 25)$	`.#######.....`	0	6	203
$y \geqslant 25$	（空）	25	0	228

看几个具体的格：相邻两行 [0, 4) 与 [4, 8) 相比，只有下标 4、5 的两条条带（左端点 $5$ 与 $10$ ）从 # 翻成 .，宽度 $5 + 5 = 10$ ，正好等于该行的水平边 10——这就是矩形之间「凹进去」的那一段轮廓。竖直边随高度缩放也很直观：[10, 14) 行的 cover 是 .########.###，左端空、右端满、内部还有 3 处跳变，所以 border = 0 + 1 + 3 = 4，乘上高度 4 得 16。

最后一行之上还有一条完整的顶边：[22, 25) 行的覆盖条带总宽 $25$ ，在 $y = 25$ 处整条露出，于是 $203 + 25 = 228$ ，与样例答案一致。

代码

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#!/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-01 08:40
# update_at: 2026-10-01 08:40

# x、y 上只有 2N 个坐标会真正切开覆盖状态，其余整数都夹在中间陪跑；压成条带之后，
# 相邻两行只差几个事件，于是「逐行比较覆盖状态」可以整段交给 numpy 向量化。

import sys

import numpy as np


def compress(lo: np.ndarray, hi: np.ndarray) -> tuple[np.ndarray, np.ndarray, np.ndarray]:
    """一维坐标压缩：返回 (每条带的真实宽度, 每条带起点下标, 终点下标)。"""
    edges = np.unique(np.concatenate((lo, hi)))     # 只有这些坐标会切开覆盖状态
    return np.diff(edges), np.searchsorted(edges, lo), np.searchsorted(edges, hi)


def events_by_row(
    Y: np.ndarray, Y2: np.ndarray, X: np.ndarray, X2: np.ndarray, ny: int
) -> tuple[np.ndarray, np.ndarray, np.ndarray]:
    """把 4N 个扫描线事件按 y 区间分桶，返回 (差分位置, 增量, 桶边界)。

    每个矩形贡献四个事件：进入时在左端 +1、右端 -1，离开时施加相反的一对，
    使得前缀和恰好等于「该 y 区间内被覆盖的条带」。
    """
    sign = np.ones(len(Y), dtype=np.int64)
    row = np.concatenate((Y, Y, Y2, Y2))            # 依次对应下面 4 个事件块
    pos = np.concatenate((X, X2, X, X2))
    inc = np.concatenate((sign, -sign, -sign, sign))
    order = np.argsort(row, kind='stable')          # 按行分桶，同一行事件之间的次序无关
    pos, inc = pos[order], inc[order]
    bounds = np.searchsorted(row[order], np.arange(ny + 1))   # 第 i 行的事件是 [bounds[i], bounds[i+1])
    return pos, inc, bounds


def perimeter(
    pos: np.ndarray, inc: np.ndarray, bounds: np.ndarray, dx: np.ndarray, dy: np.ndarray
) -> int:
    """自下而上扫描，累加轮廓：水平边看相邻两行的差异，竖直边看行内的翻转。"""
    level = np.zeros(len(dx) + 1, dtype=np.int64)   # x 方向差分；末尾一格接「最右端之后的 -1」
    prev = np.zeros(len(dx), dtype=bool)            # 上一行的覆盖状态，最下面一行的下面是空的
    ans = 0
    for i in range(len(dy)):
        lo, hi = bounds[i], bounds[i + 1]
        np.add.at(level, pos[lo:hi], inc[lo:hi])    # 逐事件累加，同一条带上的多个事件不能互相覆盖
        cover = np.cumsum(level[:len(dx)]) > 0
        horizontal = int(dx[cover != prev].sum())   # 与上一行状态不同的条带，整段露出水平边
        border = int(cover[0]) + int(cover[-1]) + int(np.count_nonzero(cover[1:] != cover[:-1]))
        ans += horizontal + int(dy[i]) * border     # 竖直边 = 本行左右两端 + 行内翻转处
        prev = cover
    return ans + int(dx[prev].sum())                # 最上面一行之上没有矩形，顶部整条边界都算


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    rects = np.array(
        [(next(data), next(data), next(data), next(data)) for _ in range(n)],
        dtype=np.int64,
    )                                                  # 左下角、右上角拆成四列
    x1, y1, x2, y2 = rects.T

    dx, X, X2 = compress(x1, x2)
    dy, Y, Y2 = compress(y1, y2)
    pos, inc, bounds = events_by_row(Y, Y2, X, X2, len(dy))
    print(perimeter(pos, inc, bounds, dx, dy))


if __name__ == "__main__":
    solve()

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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170/**
 * 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-06 13:03
 * update_at: 2026-10-06 13:03
 */
#include <algorithm>
#include <cstdio>
#include <cstring>

typedef long long ll;

const int MAXN = 5005;

int n;                          // 矩形个数
ll raw_x1[MAXN], raw_y1[MAXN];  // 每个矩形左下角
ll raw_x2[MAXN], raw_y2[MAXN];  // 每个矩形右上角
ll xs[2 * MAXN], ys[2 * MAXN];  // x、y 方向上出现过的所有坐标（排序去重后）
int kx, ky;                     // xs、ys 去重后的坐标个数

ll dx[2 * MAXN], dy[2 * MAXN];  // dx[j]：第 j 条 x 带宽度；dy[i]：第 i 条 y 带高度
int bx1[MAXN], by1[MAXN];       // 每个矩形左/下边界所在带的起点在 xs/ys 中的下标
int bx2[MAXN], by2[MAXN];       // 每个矩形右/上边界所在带的终点在 xs/ys 中的下标

// 扫描线事件：第 row 条 y 带开始时，x 差分位置 pos 增加 inc
struct Event {
    int row;
    int pos;
    int inc;
};
Event ev[4 * MAXN];             // 每个矩形贡献 4 个事件，一共 4N 个
int ev_cnt;

ll level[2 * MAXN];             // x 方向差分数组，末尾多留一格接最右端之后的 -1
bool cover[2 * MAXN];           // 当前 y 带上每条 x 带是否被覆盖
bool prev_cover[2 * MAXN];      // 上一条 y 带的覆盖状态，最下面一行的下方视为全空

bool cmp_event(const Event &a, const Event &b) {
    return a.row < b.row;
}

// 对一维坐标排序去重，返回去重后的坐标个数，结果写回 arr
int unique_coords(ll *arr, int len) {
    std::sort(arr, arr + len);
    int k = 0;
    for (int i = 0; i < len; i++) {
        if (k == 0 || arr[i] != arr[k - 1]) {
            arr[k] = arr[i];
            k++;
        }
    }
    return k;
}

// 在去重后的坐标数组 arr（长度 k）中查找数值 v 的下标
int find_index(ll *arr, int k, ll v) {
    int lo = 0;
    int hi = k - 1;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (arr[mid] < v) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return lo;
}

int main() {
    if (scanf("%d", &n) != 1) {
        return 0;
    }
    for (int i = 1; i <= n; i++) {
        scanf("%lld%lld%lld%lld", &raw_x1[i], &raw_y1[i], &raw_x2[i], &raw_y2[i]);
        xs[2 * i - 2] = raw_x1[i];
        xs[2 * i - 1] = raw_x2[i];
        ys[2 * i - 2] = raw_y1[i];
        ys[2 * i - 1] = raw_y2[i];
    }

    // 坐标压缩：只有这些坐标会切开覆盖状态，条带内部的格子状态一致
    kx = unique_coords(xs, 2 * n);
    ky = unique_coords(ys, 2 * n);

    int nx = kx - 1;  // x 方向条带数
    int ny = ky - 1;  // y 方向条带数
    for (int j = 0; j < nx; j++) {
        dx[j] = xs[j + 1] - xs[j];
    }
    for (int i = 0; i < ny; i++) {
        dy[i] = ys[i + 1] - ys[i];
    }

    for (int i = 1; i <= n; i++) {
        bx1[i] = find_index(xs, kx, raw_x1[i]);
        bx2[i] = find_index(xs, kx, raw_x2[i]);
        by1[i] = find_index(ys, ky, raw_y1[i]);
        by2[i] = find_index(ys, ky, raw_y2[i]);
    }

    // 每个矩形拆成 4 个事件：进入时左端 +1、右端 -1，离开时施加相反的一对
    ev_cnt = 0;
    for (int i = 1; i <= n; i++) {
        ev[ev_cnt].row = by1[i]; ev[ev_cnt].pos = bx1[i]; ev[ev_cnt].inc = 1;  ev_cnt++;
        ev[ev_cnt].row = by1[i]; ev[ev_cnt].pos = bx2[i]; ev[ev_cnt].inc = -1; ev_cnt++;
        ev[ev_cnt].row = by2[i]; ev[ev_cnt].pos = bx1[i]; ev[ev_cnt].inc = -1; ev_cnt++;
        ev[ev_cnt].row = by2[i]; ev[ev_cnt].pos = bx2[i]; ev[ev_cnt].inc = 1;  ev_cnt++;
    }
    std::sort(ev, ev + ev_cnt, cmp_event);

    memset(level, 0, sizeof(level));
    memset(prev_cover, 0, sizeof(prev_cover));

    ll ans = 0;
    int ptr = 0;
    for (int row = 0; row < ny; row++) {
        // 把落在当前 y 带的事件累加到 x 差分数组上（同一位置可能叠加多个事件）
        while (ptr < ev_cnt && ev[ptr].row == row) {
            level[ev[ptr].pos] += ev[ptr].inc;
            ptr++;
        }

        // 对差分数组做前缀和，得到本行的覆盖状态
        ll running = 0;
        for (int j = 0; j < nx; j++) {
            running += level[j];
            cover[j] = running > 0;
        }

        // 水平边：与上一行状态不同的条带，整段露出边界
        ll horizontal = 0;
        for (int j = 0; j < nx; j++) {
            if (cover[j] != prev_cover[j]) {
                horizontal += dx[j];
            }
        }

        // 竖直边：本行左右两端 + 行内状态翻转处，乘以行高
        ll border = 0;
        if (cover[0]) {
            border++;
        }
        if (cover[nx - 1]) {
            border++;
        }
        for (int j = 1; j < nx; j++) {
            if (cover[j] != cover[j - 1]) {
                border++;
            }
        }

        ans += horizontal + dy[row] * border;

        for (int j = 0; j < nx; j++) {
            prev_cover[j] = cover[j];
        }
    }

    // 最上面一行之上没有矩形，顶部整条边界都要累加
    for (int j = 0; j < nx; j++) {
        if (prev_cover[j]) {
            ans += dx[j];
        }
    }

    printf("%lld\n", ans);
    return 0;
}

复杂度

设 $k_x \leqslant 2N$ 、 $k_y \leqslant 2N$ 为压缩后的条带数。

时间：坐标压缩与事件排序 $O(N \log N)$ ；逐行扫描每行对本行事件做一次差分累加、对长度 $k_x$ 的数组做一次前缀和，合计 $O(N + k_x k_y) = O(N \log N + N^2)$ 。
空间：level、prev、cover 与四个事件数组都是 $O(N)$ ，不随坐标值域增长。

在 $N = 5000$ 时 $k_x k_y$ 的理论上界约 $10^8$ ，实际上界只在坐标极度分散时才会接近；内层全部由 numpy 向量化完成，实测真实数据单点耗时不超过 0.06 s、峰值内存约 30 MB。

总结

压缩坐标：把 $20001$ 个整数坐标压到只有 $2N$ 个「会被矩形的边切到」的条带，平面变成 $(2N-1)^2$ 的小网格，压缩不丢信息。
换视角：轮廓长度 = 逐行比较覆盖状态后翻转的总量。水平边来自「相邻两行状态不同的条带」，竖直边来自「同一行内部状态翻转处 × 高度」。
扫描线：因为压缩后的矩阵可能仍有 $10^8$ 格，用 4 个事件 + x 方向差分数组按行流式处理，只保留长度 $O(N)$ 的数组。
同类思路（矩形面积并、矩形周长并、扫描线 + 离散化）在更难的题里会继续出现，这里的「状态翻转」是最基础的一层。
用 Python 落地时善用 numpy 的 cumsum、比较和布尔索引，把原本 $O(k_x)$ 的内层循环整段向量化；C++ 落地用排序事件 + 手写前缀和即可，不需要 numpy。

图示解析

这张图串起从建模到得到答案的主线：

text

1
2
3
4
5
6N 个矩形
`- 坐标压缩：x1/x2/y1/y2 切成 O(N) 个条带（条带内状态一致）
   `- 关键观察：轮廓 = 覆盖状态的翻转
      |- 水平：相邻两个 y 区间上状态不同的条带，累加 dx
      `- 竖直：区间内 cover 的翻转数 border × 高度 dy
         `- 不建矩阵：4 个事件 + x 差分数组逐行流式扫描，最后顶部封口

先看「坐标压缩」这一步为什么无损（条带内状态一致），再看两类翻转分别对应哪种边界，最后确认扫描线只是把「逐行算 cover」变成不存矩阵的流式写法。图中每一层都是正文已经推导过的结论，不替代上面的样例推演和正确性说明。