扫描线算法矩形面积并线段树与扫描线结合-尧图网站建设

📅 发布时间：2026/6/20 11:35:17

关键是理解这里点对应的是一个区间，用来表示一段线段长度。

要解决矩形面积并问题，高效的方法是扫描线算法结合线段树离散化，能处理高达 105 个矩形的规模。

核心结论

扫描线算法通过 “竖线扫描 + 区间更新” 计算面积并，时间复杂度 O(nlogn)，核心是将 y 轴坐标离散化，用线段树维护区间覆盖长度。

关键原理

扫描线思想：用垂直于 x 轴的直线从左到右扫描，记录矩形左右边界（左边界 + 1 标记，右边界 - 1 标记）。
离散化处理：y 轴坐标范围可能达 10^9，需将所有 y 坐标去重排序，映射为紧凑索引（减少线段树规模）。
线段树功能：维护 y 轴区间的覆盖次数和有效长度，支持区间更新（加减覆盖次数）和查询（当前有效覆盖长度）。

实现步骤

1. 数据预处理

提取所有矩形的 y1、y2 坐标，去重后排序得到离散化数组。
将每个矩形拆分为两条扫描线：左边界（x1，y1，y2，+1）和右边界（x2，y1，y2，-1）。
按扫描线的 x 坐标升序排序（x 相同则先处理减标记，避免重复计算）。

2. 线段树实现

节点存储：区间覆盖次数（cnt）、区间有效覆盖长度（len）。
区间更新：给 [y1, y2) 区间的 cnt 加减 1，更新时根据 cnt 是否大于 0 维护 len（cnt>0 则 len 为区间长度，否则递归合并子节点 len）。
注意：离散化后的 y 区间是 “左闭右开”，避免边界重复计算。

3. 扫描计算面积

初始化前一条扫描线的 x 坐标（prev_x）和面积总和（ans）。
遍历排序后的扫描线：
1. 计算当前扫描线与 prev_x 的水平距离（dx = x - prev_x）。
2. 若 dx>0，累加面积（ans += dx * 线段树查询的有效长度）。
3. 用当前扫描线的标记更新线段树的 y 区间。
4. 更新 prev_x 为当前 x 坐标。

https://www.bilibili.com/video/BV16x4y1a7Ro/
https://www.bilibili.com/video/BV1MX4y1Z7N5

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;const int MAXN = 2e5 + 10;  // n<=1e5，每条矩形拆2条线，共2e5条扫描线// 扫描线结构体：x坐标、y1、y2（原始坐标）、标记（+1左边界/-1右边界）
struct Line {int x, y1, y2, val;Line() {}Line(int x_, int y1_, int y2_, int val_) : x(x_), y1(y1_), y2(y2_), val(val_) {}// 排序规则：x升序，x相同则减标记在前（避免重复计算）bool operator<(const Line& rhs) const {if (x != rhs.x) return x < rhs.x;return val < rhs.val;}
};// 线段树节点：覆盖次数cnt、有效长度len
struct Node {int l, r, cnt;long long len;
} tree[MAXN << 2];  // 离散化后y坐标最多2e5个，线段树需4倍空间vector<int> ys;  // 存储所有y坐标，用于离散化// 构建线段树（l、r为离散化后的索引区间）
void build(int root, int l, int r) {tree[root].l = l;tree[root].r = r;tree[root].cnt = 0;tree[root].len = 0;if (l == r) return;int mid = (l + r) >> 1;build(root << 1, l, mid);build(root << 1 | 1, mid + 1, r);
}// 向上更新：根据子节点计算当前节点的有效长度
void push_up(int root) {int l = tree[root].l, r = tree[root].r;if (tree[root].cnt > 0) {// 覆盖次数>0，有效长度为原始y区间长度tree[root].len = ys[r + 1] - ys[l];//*** 右边要加1 *** } else if (l == r) {//下面都是无覆盖情况// 叶子节点且无覆盖，长度为0tree[root].len = 0;} else {// 非叶子节点，合并左右子节点长度tree[root].len = tree[root << 1].len + tree[root << 1 | 1].len;}
}// 区间更新：给离散化后的[y1_idx, y2_idx]区间加减val
void update(int root, int L, int R, int val) {int l = tree[root].l, r = tree[root].r;if (L <= l && r <= R) {tree[root].cnt += val;push_up(root);return;}int mid = (l + r) >> 1;if (L <= mid) update(root << 1, L, R, val);if (R > mid) update(root << 1 | 1, L, R, val);push_up(root);
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;vector<Line> lines;lines.reserve(2 * n);for (int i = 0; i < n; ++i) {int x1, y1, x2, y2;cin >> x1 >> y1 >> x2 >> y2;lines.emplace_back(x1, y1, y2, 1);lines.emplace_back(x2, y1, y2, -1);ys.push_back(y1);ys.push_back(y2);}// 离散化y坐标：去重+排序sort(ys.begin(), ys.end());ys.erase(unique(ys.begin(), ys.end()), ys.end());int m = ys.size();if (m <= 1) {  // 无有效y区间，面积为0cout << 0 << endl;return 0;}// 构建线段树（离散化索引范围0~m-2，对应ys[0]~ys[m-1]的区间）build(1, 0, m - 2);// 排序扫描线sort(lines.begin(), lines.end());long long ans = 0;int prev_x = -1;  // 前一条扫描线的x坐标for (auto& line : lines) {int x = line.x, y1 = line.y1, y2 = line.y2, val = line.val;if (prev_x != -1 && x > prev_x) {// 累加面积：水平距离 * 当前有效覆盖长度ans += 1LL * (x - prev_x) * tree[1].len;}// 找到y1和y2在离散化数组中的索引int l = lower_bound(ys.begin(), ys.end(), y1) - ys.begin();int r = lower_bound(ys.begin(), ys.end(), y2) - ys.begin() - 1;// *** 要减1 ***if (l <= r) {update(1, l, r, val);}prev_x = x;}cout << ans << endl;return 0;
}

扫描线算法 矩形面积并 线段树与扫描线结合