扫描线|离散化|线段树+二分

lc

扫描线模板（矩形面积并）

线段树+二分

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

typedef long long ll;
const int N = 2010;

// 边的事件结构体：存储扫描线的入边/出边信息
struct Edge {
ll x, y1, y2;
int k; //入边k=1（覆盖+1），出边k=-1（覆盖-1）
Edge() {}
Edge(ll x, ll y1, ll y2, int k) : x(x), y1(y1), y2(y2), k(k) {}
// 事件点排序规则：按x坐标升序，x相同则入边优先（保证先加后减，避免漏算）
bool operator<(const Edge& t) const {
returnx < t.x;
}
};

Edge e[N << 1];
ll y[N << 1]; // 存储所有y坐标，用于离散化
int cnt;

// 线段树：维护当前扫描线覆盖的y轴区间有效长度
struct Node {
int l, r;
int cnt; // 区间被覆盖的次数
ll len; // 区间的有效长度（被覆盖时的长度）
} tr[N << 3];

void build(int u, int l, int r) {
tr[u] = {l, r, 0, 0};
if (l == r) return;
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
}

// 向上更新：根据子节点和当前覆盖次数计算有效长度
void pushup(int u) {
if (tr[u].cnt) tr[u].len = y[tr[u].r + 1] - y[tr[u].l];
else if (tr[u].l == tr[u].r) tr[u].len = 0;
else tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
}

// 线段树区间更新：修改覆盖次数
void update(int u, int l, int r, int k) {
if (tr[u].l >= l && tr[u].r <= r) {
tr[u].cnt += k;
pushup(u);
return;
}
int mid = tr[u].l + r >> 1;
if (l <= mid) update(u << 1, l, r, k);
if (r > mid) update(u << 1 | 1, l, r, k);
pushup(u);
}

// 计算n个矩形的面积并
ll rectangleArea(vector<vector<ll>>& rects) {
cnt = 0;
int n = rects.size();
for (auto& rect : rects) {
ll x1 = rect[0], y1 = rect[1], x2 = rect[2], y2 = rect[3];
// 1. 构建事件点：左边界是入边，右边界是出边
e[cnt++] = Edge(x1, y1, y2, 1);
e[cnt++] = Edge(x2, y1, y2, -1);
// 收集所有y坐标，用于后续离散化
y[cnt - 2] = y1;
y[cnt - 1] = y2;
}

// ========== 离散化代码 start
sort(y, y + cnt); // 排序y坐标
// 去重：得到离散化后的唯一y坐标数量
int m = unique(y, y + cnt) - y;
// ========== 离散化代码 end

sort(e, e + cnt); // 按x坐标升序排序事件点
// ========== 事件点排序

build(1, 0, m - 2); // 线段树的叶子节点对应y[i]到y[i+1]的区间
ll res = 0;
for (int i = 0; i < cnt; i++) {
// 相邻事件点的x差 × 当前有效长度 = 这一段的面积
if (i > 0) res += tr[1].len * (e[i].x - e[i - 1].x);
// 二分查找y1,y2对应的离散化下标
int l = lower_bound(y, y + m, e[i].y1) - y;
int r = lower_bound(y, y + m, e[i].y2) - y;
// 更新线段树：覆盖区间[l, r-1]
update(1, l, r - 1, e[i].k);
}
return res;
}

说明

1. 离散化作用：把大范围的 y 坐标映射到小范围的下标，避免线段树空间爆炸，是处理大坐标的必备操作
2. 事件点排序核心作用：保证扫描线从左到右依次处理，入边先于出边的规则能避免同一 x 位置先减后加导致的有效长度计算错误