扫描线
定义
将静态\(N\)维度问题，降维转化为\(N-1\)维动态局部子问题，利用数据结构维护状态，在各个事件点处做贡献或者转移，最终得到全局答案的算法。
一般展开
-
确定事件和时间轴
将高维问题的元素收集(如几何边界，转移，物品出现/消失)，按主维度(如 \(x\) 轴，时间)排序，转化为低维时间轴上的离散事件点。
-
动态维护状态截面
扫描线在时间轴上推进，每遇上一个事件点，就利用数据结构在截面上执行相应的状态修改(如线段覆盖，\(DP\)状态转移)。
-
贡献计算
在各个事件点间，通过"当前截面状态 \(\times\) 时间轴推进距离"计算局部贡献(如面积)，或者进行\(DP\)转移，累计得到全局解。
例题
P5490 【模板】扫描线 & 矩形面积并 - 洛谷
-
题目大意
求 \(n\) 个四边平行于坐标轴的矩形的面积并。
-
思路
将每个矩形拆解成 \(x = x_1\) 的入边和 \(x = x_2\) 的出边，以 \(x\) 轴作为主轴向右扫描。
用线段树维护 \(y\) 轴上的区间。线段树节点记录 \(cnt\) 和 \(len\) (区间覆盖次数 和 区间实际覆盖长度)，在push_up中计算处理(当 \(cnt\) 为 \(0\) 时将 \(len\) 置为 \(0\)；否则将 \(len\) 置为区间长度)。只用查询整个截面的有效长度，只查询根节点，无需 push_down。
const ll N = 2e5 + 9;
class Segment{struct {// cnt: 区间被覆盖次数，len: 区间长度，sum: 有效长度ll cnt = 0, len = 0, sum = 0;}t[N << 2];#define ls (i << 1)#define rs (i << 1 | 1)#define mid (l + r >> 1)// 重点void up(ll i, ll l, ll r) {// 当整个区间有效，有效长度取整个区间长度if(t[i].cnt > 0) t[i].sum = t[i].len;// 当整个区间无效，若为叶区间，取 0else if(l == r) t[i].sum = 0;// 否则有效长度取两个子区间有效区间和else t[i].sum = t[ls].sum + t[rs].sum;}public:// 初始化区间长度，重置各个区间信息void build(ll i, ll l, ll r, vector<ll>& a) {if(l == r) {t[i].len = a[l];t[i].cnt = t[i].sum = 0;return;}t[i].cnt = t[i].sum = 0;build(ls, l, mid, a);build(rs, mid+1, r, a);t[i].len = t[ls].len + t[rs].len;}void update(ll i, ll l, ll r, ll L, ll R, ll v) {if(L <= l && r <= R) {// 区间覆盖次数改变t[i].cnt += v;// 处理节点信息up(i, l, r);return;}if(L <= mid) update(ls, l, mid, L, R, v);if(mid+1<=R) update(rs, mid+1, r, L, R, v);// 处理节点信息up(i, l, r);}// 返回整个截面有效长度ll query() {return t[1].sum;}
}seg;void bluket() {ll n = rd;// 收集x坐标, 转化事件vector<ll> xs; vector<array<ll, 4>> opt(2 * n);for (int i = 0; i < n; i++) {ll x1 = rd, y1 = rd, x2 = rd, y2 = rd;opt[i << 1] = {x1, x2, y1, 1};opt[i << 1 | 1] = {x1, x2, y2, -1};xs.push_back(x1); xs.push_back(x2);}// 离散化截面上的坐标sort(all(xs));xs.erase(unique(all(xs)), xs.end());auto mp = [&](ll x) { return lower_bound(all(xs), x) - xs.begin() + 1; };// 计算区间长度ll m = xs.size() - 1;vector<ll> len(m + 1);for (int i = 0; i + 1 < xs.size(); i++)len[i+1] = xs[i+1] - xs[i]; // 用区间长度建树 seg.build(1, 1, m, len);// 按主轴排序事件sort(all(opt), [](auto u, auto v){ return u[2] < v[2]; });ll ans = 0;for(int i = 0; i < 2 * n; i++) {auto [x1, x2, y, op] = opt[i];// 这里仅当 opt[i][2] - opt[i-1][2] 不为 0 即 两次事件不在同一 y坐标上有效// y 轴区间长度 乘上 截面有效长度 得到相应部分贡献if(i > 0) ans += (opt[i][2] - opt[i-1][2]) * seg.query();// 将坐标信息转化为区间信息ll L = mp(x1);ll R = mp(x2) - 1;// 更新截面信息seg.update(1, 1, m, L, R, op);} P(ans);
}