1. 项目概述与问题拆解“油漆面积”这个题目乍一看名字挺生活化但做过蓝桥杯或者信奥赛题的朋友都知道这绝对是个“坑”不少的经典题目。它本质上是一个计算几何问题核心是求解平面上多个矩形覆盖的总面积。听起来简单不就是把每个矩形的面积加起来吗但问题就在于矩形之间会重叠直接相加会导致重叠部分被重复计算。这就是题目的核心难点也是区分选手算法功底的关键。这道题源自蓝桥杯2017年省赛A组在信奥信息学奥林匹克的刷题体系中它编号P8648属于考察基础算法思想和编码实现能力的典型题目。对于正在备赛蓝桥杯或信奥的C选手来说攻克这类题目至关重要。它不仅仅考察你对循环、数组等基础语法的掌握更深入考察你是否能灵活运用扫描线、离散化、差分数组等算法思想来高效、准确地解决实际问题。我当年第一次碰到这类题时也想过用最朴素的思路开一个足够大的二维布尔数组把每个矩形覆盖的区域标记为true最后统计true的个数。这个方法在理论上是可行的对于教学演示理解问题本质很有帮助。但稍微一分析就知道题目中坐标范围可能很大比如达到10^4级别如果开一个10000*10000的数组内存消耗巨大约100MB且双重循环标记和统计的时间复杂度是O(N * W * H)在矩形数量多、面积大时必然超时。所以这个“笨办法”只能帮助我们理解题意绝不能作为竞赛的解决方案。接下来我们就从暴力法开始一步步推导出高效的正解。2. 核心思路与算法选型分析面对矩形面积并的问题我们需要一个能处理重叠、且效率足够高的算法。常见的思路有以下几种我们来逐一分析其优劣和适用场景。2.1 暴力模拟法理解基础不可用于竞赛正如前面提到的我们可以将坐标系视为一个巨大的网格。假设所有坐标都是整数题目通常如此我们可以创建一个二维数组canvas[x][y]初始化为false。对于输入的每个矩形(x1, y1, x2, y2)我们遍历x从x1到x2-1y从y1到y2-1的所有整数点将对应的canvas[x][y]标记为true。最后遍历整个画布统计true的个数即为总面积。为什么这个方法不行空间复杂度高坐标范围若为0到10000需要10001*10001≈1e8个布尔变量。一个bool在C中通常占1字节这需要约100MB内存远超一般竞赛环境限制通常256MB或更低。时间复杂度高对于N个矩形每个矩形平均面积为S那么标记操作的时间复杂度接近O(N * S)统计又是O(范围^2)。在N较大时完全不可接受。注意这个方法是帮助我们具象化问题的“教学工具”。在向初学者解释题意时用它来画图演示非常直观。但在任何追求效率的场合必须立即抛弃。2.2 扫描线算法经典正解这是解决矩形面积并问题的标准算法核心思想是“化面为线”。我们想象有一根垂直的线从最左侧扫到最右侧。离散化由于坐标可能很大我们只关心所有矩形竖边的x坐标。将这些x坐标排序去重得到一系列离散的“区间”。任意两个相邻x坐标之间的区域内部没有矩形的竖边穿过因此该区域内被矩形覆盖的“高度”是恒定不变的。事件处理将每个矩形看作两个“事件”左边缘x1是“进入”事件表示从此处开始矩形对[y1, y2)区间有贡献右边缘x2是“离开”事件表示从此处结束贡献。线段树维护当扫描线移动到某个x位置时我们处理所有发生在这个x坐标上的事件可能是多个矩形的进入或离开。处理事件意味着更新线段树对于“进入”事件将区间[y1, y2)的覆盖次数1对于“离开”事件则-1。面积累加在处理完某个x位置的所有事件后线段树根节点记录了当前扫描线位置处被覆盖的“总高度”即有效覆盖的y轴长度。这个高度乘以当前x区间next_x - current_x的宽度就是这一小竖条的面积。累加所有这样的竖条面积得到最终结果。为什么扫描线是正解它的时间复杂度为O(N log N)其中N是矩形数量。离散化将连续的x轴压缩为2N个关键点线段树维护y轴区间覆盖每次更新和查询都是O(log Y)Y是y坐标离散化后的点数。效率非常高能够处理大规模数据。2.3 差分数组离散化更易实现的替代方案对于蓝桥杯省赛这个级别的题目数据范围有时可能被设计得可以让一种更简单的方法通过即“差分数组离散化”或者叫“二维差分”的离散化版本。对坐标离散化分别收集所有x坐标和y坐标排序、去重。这样我们将整个平面划分为(nx-1) * (ny-1)个小格子其中nx和ny是离散化后x和y坐标的个数。构建差分数组创建一个二维数组diff[nx][ny]初始为0。对于每个矩形我们找到其四个边在离散化坐标数组中的索引(idx_x1, idx_y1, idx_x2, idx_y2)。然后执行二维差分标记diff[idx_x1][idx_y1] 1; diff[idx_x1][idx_y2] - 1; diff[idx_x2][idx_y1] - 1; diff[idx_x2][idx_y2] 1;前缀和还原与面积计算对diff数组求二维前缀和得到sum[i][j]它表示小格子(i, j)对应原坐标系中[x[i], x[i1]) x [y[j], y[j1])区域被矩形覆盖的次数。如果sum[i][j] 0那么这个格子被覆盖。这个格子的实际面积是(x[i1] - x[i]) * (y[j1] - y[j])。累加所有被覆盖格子的面积即可。这个方法与扫描线的对比优点思维难度较低代码实现比线段树版本的扫描线简单不易出错。缺点空间复杂度为O(N^2)因为diff数组大小是(2N) * (2N)级别。当N很大比如 1000时可能会超出内存限制。时间复杂度是O(N^2)在N较大时也可能超时。适用性在蓝桥杯本题的官方测试数据下由于N最大为10000纯粹的O(N^2)差分是不可行的。但是如果题目给出的矩形坐标是整数且范围不大例如本题中坐标在0到10000之间我们可以利用这个范围直接开一个10001*10001的差分数组吗前面分析过这需要约100MB的int数组4字节每个内存可能勉强在边界但时间上1e8量级的操作仍然非常危险。因此对于本题扫描线算法是更稳妥、更通用的选择。考虑到普适性和教学价值本文将重点讲解扫描线算法的实现并会提到差分思想作为对比和补充理解。3. 扫描线算法C实现详解我们将一步步实现扫描线算法。为了让代码清晰且高效我们需要定义几个关键的数据结构和步骤。3.1 数据结构定义与事件处理首先我们需要表示一个“事件”。每个矩形产生两个事件。#include iostream #include vector #include algorithm using namespace std; // 定义事件结构体 struct Event { int x; // 事件发生的x坐标 int y1, y2; // 事件影响的y轴区间 [y1, y2) int type; // 事件类型1 表示矩形开始左边缘-1 表示矩形结束右边缘 Event(int _x, int _y1, int _y2, int _t) : x(_x), y1(_y1), y2(_y2), type(_t) {} // 重载小于运算符用于按x坐标排序。如果x相同通常让type为1的事件先处理确保边界正确。 bool operator (const Event other) const { if (x ! other.x) return x other.x; // 如果x相同先处理进入事件(type0)再处理离开事件(type0)避免边界计算错误 return type other.type; } };type为1表示在这个x坐标处有一个新的矩形开始覆盖区间[y1, y2)type为-1表示在这个x坐标处一个矩形停止覆盖该区间。输入所有矩形后我们生成事件列表并排序vectorEvent events; for (int i 0; i n; i) { int x1, y1, x2, y2; cin x1 y1 x2 y2; // 确保x1x2, y1y2。题目可能不保证但面积计算需要。 if (x1 x2) swap(x1, x2); if (y1 y2) swap(y1, y2); events.emplace_back(x1, y1, y2, 1); // 左边缘进入 events.emplace_back(x2, y1, y2, -1); // 右边缘离开 } sort(events.begin(), events.end());3.2 坐标离散化y坐标也需要离散化因为线段树需要建立在离散的y索引上。我们将所有事件的y1和y2收集起来。vectorint y_vals; for (const auto e : events) { y_vals.push_back(e.y1); y_vals.push_back(e.y2); } sort(y_vals.begin(), y_vals.end()); y_vals.erase(unique(y_vals.begin(), y_vals.end()), y_vals.end()); int y_cnt y_vals.size(); // 离散化后y坐标的个数unique函数将排序后的向量中的相邻重复元素移到末尾并返回新的逻辑结尾的迭代器erase则删除这些重复项。现在y_vals存储了所有不同的y坐标y_vals[i]表示第i个y坐标的实际值。我们需要一个函数将实际的y坐标值映射到它在y_vals中的索引从0开始。同时线段树节点维护的是y坐标的区间索引即[idy1, idy2)表示覆盖了原y轴从y_vals[idy1]到y_vals[idy2]的区域。3.3 线段树节点设计这里的线段树不是传统的求和或最值线段树而是用于维护区间覆盖次数和有效覆盖长度。struct SegNode { int cover; // 当前区间被完整覆盖的次数 int len; // 当前区间内被覆盖的长度实际坐标值不是索引差 }; vectorSegNode tree; vectorint length; // 存储每个线段树节点对应的原始y轴长度cover表示这个节点对应的整个y区间被矩形覆盖了多少层。len表示这个节点对应的区间中至少被覆盖一次的部分的实际长度。length数组需要预计算。对于线段树中每个叶子节点对应一个y坐标点它没有“长度”。对于内部节点其length等于它左右孩子节点对应的原始y轴区间长度之和。更准确地说如果节点p对应离散化y坐标索引区间[l, r]那么它管理的原始y轴区间是[y_vals[l], y_vals[r]]。但线段树通常处理的是“点”或“单位区间”。在面积并问题中我们通常将线段树建立在y坐标的“间隙”上。一个更常见的做法是线段树的叶子节点代表第i个y区间[y_vals[i], y_vals[i1])。这样线段树的大小是y_cnt - 1。让我们调整一下离散化数据的用法。定义y_vals存储所有不同的y坐标排序后为[Y0, Y1, Y2, ..., Y_{m-1}]。那么有m-1个基本区间[Y0, Y1), [Y1, Y2), ..., [Y_{m-2}, Y_{m-1})。线段树tree的大小设为4 * (m-1)每个节点p对应一个基本区间的集合。我们需要一个函数来建立length数组对于表示区间[l, r]的节点这里l和r是基本区间的索引其length等于y_vals[r1] - y_vals[l]。对于叶子节点l r其length就是y_vals[l1] - y_vals[l]。3.4 线段树的更新与查询更新函数update接收一个离散化的y区间[ql, qr)和变化值val(1 或 -1)。它递归地更新线段树。 关键点在于如何根据cover更新len如果当前节点区间[l, r]的cover 0说明整个区间被完全覆盖那么tree[p].len length[p]即该节点对应的原始总长度。否则cover 0如果l r叶子节点则tree[p].len 0否则tree[p].len tree[left].len tree[right].len。为什么这样是正确的cover记录的是“整个区间”被覆盖的层数。只要cover 0无论下层节点状态如何这个区间都被完全覆盖了。只有当cover 0时这个区间的覆盖状态才需要由它的两个子区间的覆盖状态来决定。这是一种“懒惰”的维护方式我们不需要将覆盖信息下推到叶子节点。// 假设 y_vals, tree, length 已定义 void build(int p, int l, int r) { if (l r) { // 叶子节点对应第l个基本区间 [y_vals[l], y_vals[l1]) length[p] y_vals[l1] - y_vals[l]; tree[p].cover tree[p].len 0; return; } int mid (l r) / 2; build(p*2, l, mid); build(p*21, mid1, r); length[p] length[p*2] length[p*21]; // 内部节点的长度是子节点长度和 } void update(int p, int l, int r, int ql, int qr, int val) { if (ql l r qr) { tree[p].cover val; } else { int mid (l r) / 2; if (ql mid) update(p*2, l, mid, ql, qr, val); if (qr mid) update(p*21, mid1, r, ql, qr, val); } // 更新当前节点的len if (tree[p].cover 0) { tree[p].len length[p]; } else { if (l r) { tree[p].len 0; } else { tree[p].len tree[p*2].len tree[p*21].len; } } }注意update函数中的ql, qr是离散化后基本区间的索引。例如一个事件影响原始y区间[y1, y2)我们需要找到y1在y_vals中的索引idx1以及y2在y_vals中的索引idx2。那么更新的区间是[idx1, idx2-1]因为基本区间是[y_vals[i], y_vals[i1])。3.5 主流程与面积计算有了以上准备主流程就清晰了读取所有矩形生成事件按x排序。对y坐标离散化建立线段树。遍历排序后的事件。设prev_x为上一个处理事件的x坐标。当前事件坐标为cur_x。从prev_x到cur_x之间被覆盖的y轴总长度就是线段树根节点的len即tree[1].len。面积增量delta_area (cur_x - prev_x) * tree[1].len。累加delta_area到总面积。处理所有x坐标为cur_x的事件更新线段树调用update。将prev_x更新为cur_x。输出总面积。这里有一个细节第一个事件之前prev_x应初始化为第一个事件的x坐标这样第一次计算面积增量为0。或者可以在循环外先处理第一个事件的所有同x事件再进入循环。完整代码框架#include bits/stdc.h using namespace std; struct Event { int x, y1, y2, type; Event(int _x, int _y1, int _y2, int _t): x(_x), y1(_y1), y2(_y2), type(_t) {} bool operator (const Event other) const { if (x ! other.x) return x other.x; return type other.type; // 左边界优先 } }; struct SegNode { int cover 0; int len 0; }; const int MAXN 10005; // 事件最多2N个 vectorEvent events; vectorint y_vals; SegNode tree[8 * MAXN]; // 线段树大小通常是4*(离散化y数量-1)这里开大点 int length[8 * MAXN]; void build(int p, int l, int r) { if (l r) { length[p] y_vals[l1] - y_vals[l]; return; } int mid (l r) 1; build(p1, l, mid); build(p1|1, mid1, r); length[p] length[p1] length[p1|1]; } void update(int p, int l, int r, int ql, int qr, int val) { if (ql l r qr) { tree[p].cover val; } else { int mid (l r) 1; if (ql mid) update(p1, l, mid, ql, qr, val); if (qr mid) update(p1|1, mid1, r, ql, qr, val); } if (tree[p].cover 0) { tree[p].len length[p]; } else { if (l r) { tree[p].len 0; } else { tree[p].len tree[p1].len tree[p1|1].len; } } } int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin n; for (int i 0; i n; i) { int x1, y1, x2, y2; cin x1 y1 x2 y2; if (x1 x2) swap(x1, x2); if (y1 y2) swap(y1, y2); events.emplace_back(x1, y1, y2, 1); events.emplace_back(x2, y1, y2, -1); y_vals.push_back(y1); y_vals.push_back(y2); } if (events.empty()) { cout 0 endl; return 0; } // 离散化y坐标 sort(y_vals.begin(), y_vals.end()); y_vals.erase(unique(y_vals.begin(), y_vals.end()), y_vals.end()); int m y_vals.size(); // 不同的y坐标点数 if (m 2) { cout 0 endl; return 0; } // 建立线段树管理 m-1 个基本区间 build(1, 0, m-2); // 区间索引从0到m-2 // 处理事件 sort(events.begin(), events.end()); long long total_area 0; int prev_x events[0].x; size_t i 0; while (i events.size()) { int cur_x events[i].x; // 计算上一个x到当前x之间的面积 total_area (long long)(cur_x - prev_x) * tree[1].len; // 处理所有x坐标为cur_x的事件 while (i events.size() events[i].x cur_x) { Event e events[i]; // 找到y1和y2对应的基本区间索引 int idx1 lower_bound(y_vals.begin(), y_vals.end(), e.y1) - y_vals.begin(); int idx2 lower_bound(y_vals.begin(), y_vals.end(), e.y2) - y_vals.begin(); // 更新区间 [idx1, idx2-1] if (idx1 idx2) { // 确保区间有效 update(1, 0, m-2, idx1, idx2-1, e.type); } i; } prev_x cur_x; } cout total_area endl; return 0; }4. 关键细节、调试技巧与常见问题即使理解了算法实现时依然会遇到很多坑。下面是我在多次实现和调试中总结的经验。4.1 坐标处理与区间表示问题开闭区间混淆这是最容易出错的地方。矩形的定义通常是[x1, x2) x [y1, y2)左闭右开还是[x1, x2] x [y1, y2]全闭题目描述有时会说“左下角坐标和右上角坐标”这通常暗示是[x1, x2] x [y1, y2]。但在离散化和扫描线中使用左闭右开区间[y1, y2)更方便因为它能无缝衔接避免点被重复计算。实操建议在读取输入后如果题目给的是(x1,y1), (x2,y2)且x1x2, y1y2我们将其视为覆盖区域[x1, x2) x [y1, y2)。这样矩形的宽度是x2-x1高度是y2-y1。在离散化y坐标时我们收集的是y1和y2。线段树管理的基本区间是[y_vals[i], y_vals[i1])。当处理一个影响原始区间[y1, y2)的事件时我们在离散化数组中找到y1和y2的索引idx1和idx2。那么需要更新的线段树区间是[idx1, idx2-1]。务必检查idx1 idx2否则更新一个空区间会导致错误。4.2 线段树更新逻辑的验证update函数是核心务必理解其正确性。可以构造小数据测试只有一个矩形[0,5)x[0,5)。事件(0,0,5,1),(5,0,5,-1)。离散化后y_vals [0,5]只有一个基本区间[0,5)索引0。处理第一个事件前tree[1].len0prev_x0。处理第一个事件更新区间[0,0]即idx10, idx21, idx2-10val1。更新后节点cover1len length[1] 5。此时prev_x还是0i指向下一个事件x5。计算面积(5-0) * tree[1].len 5*525。正确。处理第二个事件更新区间[0,0]val-1。更新后cover0len0。4.3 整数溢出问题总面积可能很大。坐标范围0~10000矩形数量N最大10000最坏情况所有矩形不重叠每个矩形最大面积10^8总面积可能达到10^12量级超出了int范围约2e9。因此总面积必须使用long long类型。在计算面积增量(cur_x - prev_x) * tree[1].len时两个乘数都是int但乘积可能超过int所以应先转换为long long再相乘如(long long)(cur_x - prev_x) * tree[1].len。4.4 边界情况与特殊输入N0没有矩形面积应为0。代码中需要特判否则访问events[0].x会出错。矩形退化成线或点如果x1x2或y1y2矩形面积为0。我们的代码在读取时通过swap确保x1x2, y1y2但如果输入就是相等的交换后依然相等生成的y区间[y1, y2)长度为0。在更新线段树时idx1可能等于idx2导致更新区间无效。我们的代码中加了if (idx1 idx2)的判断避免了这个问题。更好的做法是在生成事件前就判断如果矩形面积为0则跳过该矩形。所有矩形完全相同离散化后y_vals只有两个点线段树只有一个基本区间。算法依然能正确工作。大坐标小矩形离散化能有效压缩空间。4.5 调试与测试策略自己编写测试数据是调试的关键。最小测试N1一个矩形验证面积计算是否正确。重叠测试两个完全重合的矩形面积应等于一个矩形的面积。相邻测试两个矩形边对边恰好相邻例如[0,5)x[0,5)和[5,10)x[0,5)面积应为两个矩形面积和50。这可以测试开闭区间处理是否正确。嵌套测试一个小矩形完全在一个大矩形内部面积应等于大矩形面积。复杂交叉测试多个矩形随机生成用暴力法小范围验证扫描线结果。调试输出可以在主循环中打印prev_x,cur_x,tree[1].len,delta_area观察扫描过程。也可以打印离散化后的y_vals和每个事件处理前后的线段树根节点len。5. 性能优化与替代方案探讨虽然扫描线算法已经是较优解但在实现时仍有优化空间。5.1 线段树的非递归实现递归线段树在深度较大时可能有栈溢出风险虽然本题m不超过20000深度约15风险很小。非递归迭代线段树zkw线段树常数更小代码更紧凑。但对于维护区间覆盖的线段树非递归实现pushUp操作需要从叶子节点向上更新写起来稍复杂。在竞赛中递归版本清晰易懂通常足够快。5.2 使用“差分离散化一维扫描”的混合方法回忆之前提到的差分思想。我们可以只对y轴离散化然后在x方向进行扫描。离散化y坐标得到m个点构成m-1个基本区间。对于每个离散化的x区间[x_i, x_{i1})我们想知道在这个竖条里有哪些y区间被覆盖。我们可以维护一个一维数组cover[m-1]表示每个基本y区间被覆盖的次数。如何更新cover数组对于每个事件(x, y1, y2, type)我们找到其影响的y区间索引[idx1, idx2-1]然后直接遍历这个区间对每个cover[k] type。这个操作是O(m)的。扫描所有排序后的x坐标对于每个x区间先计算当前cover数组中cover[k]0的基本区间的总长度乘以x区间宽度累加到面积。然后处理所有发生在当前x坐标上的事件更新cover数组。复杂度分析有O(N)个x区间每个区间内更新cover是O(m)总复杂度O(N * m)。在N和m都达到10000时1e8操作可能超时但比纯二维差分好。这种方法代码简单不易写错在数据随机、m不太大时可能通过。但对于极限数据扫描线线段树的O(N log m)更优。5.3 内存优化我们使用了全局固定大小的数组tree[8*MAXN]和length[8*MAXN]。MAXN是事件数量的上限2NN10000所以MAXN20000线段树大小8*20000160000两个数组都是int类型总内存约160000*4*2 ≈ 1.28MB非常小。离散化数组y_vals最多2N20000个int约80KB。内存使用很安全。6. 从本题延伸的算法学习建议“油漆面积”是一个经典的模型题。掌握它你就掌握了扫描线算法和线段树维护区间覆盖这两个强大工具。这个组合可以解决很多变种问题矩形周长并计算所有矩形并集的周长。思路类似扫描线过程中覆盖长度的变化量就是竖边周长同时还需要维护连续区间的段数来计算横边周长。三维立方体体积并从扫描线扩展到扫描面需要二维线段树或树套树难度大增。矩形覆盖最多层数求平面上被矩形覆盖次数最多的点的覆盖次数。线段树节点可以额外维护一个max_cover。动态矩形添加/删除在线问题需要支持随时增加或删除一个矩形并询问当前总面积。需要更复杂的线段树持久化或分块。对于信奥和蓝桥杯备赛我建议理解优先于背诵彻底弄懂扫描线为什么能化二维为一维线段树如何通过cover和len维护覆盖信息。亲手实现抛开题解自己从零实现一遍。调试过程能暴露你理解上的所有盲点。总结模板将扫描线线段树求面积并的代码整理成自己的模板。注意模板的通用性如坐标范围、是否需要long long。多做变式题在洛谷、AcWing等OJ上搜索“矩形面积并”、“扫描线”相关题目进行巩固。最后关于编码本身。在竞赛中我习惯将线段树的build,update,pushUp逻辑封装在一个类里主程序尽量简洁。确保使用ios::sync_with_stdio(false); cin.tie(0);来加速输入输出因为本题输入量可能较大。变量名尽量有意义但比赛时也可以使用短变量名以加快编码速度前提是自己要非常熟悉代码逻辑。这道题从理解到完全实现无误可能需要几个小时甚至更长时间。但一旦啃下来你对线段树的应用和扫描线思想的理解会上一个大台阶。这种付出是绝对值得的因为它不仅是解决一道题更是掌握了一类问题的通用武器。