今天初步的学习了一下有关扫描线的相关知识。由于本人的做题量还不够大，理解也并不很深刻，所以这篇文章还是留给自己看吧~ 扫描线，顾名思义就是用一根线在一个平面上扫描，扫到线段 / 矩形的时候就将其所含有的信息从数据结构中删去 / 加入数据结构。
通过这两道题目，可以大致的感受到扫描线的作用与神奇之处。
T1.HDU 1542 Atlantis
求多个矩形的面积并。我们可以维护一条与x轴平行的扫描线，不断移动扫描线，在遇到一条新的边的时候就将扫描线与边的高度差 * 扫描线上被边覆盖的长度加到答案中（可以画图感受一下）。问题转化为：如何统计扫描线上被边覆盖的长度？我们可以让线段树上的节点 \(l\) 表示 \(id[l]\) 到 \(id[r]\) 这一段区间。那么对于一段管辖 \(l --> r\) 的区间，我们可以维护两个值：一个值是这个区间被覆盖的次数（完整覆盖），另一个则是这个区间一共被覆盖的长度。如果这个区间被完整覆盖过，显然一共被覆盖的长度就是区间的总长。但倘若没有，那么就继承儿子的信息。这样就可以统计出扫描线上被覆盖的长度了。
#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> using namespace std; #define maxn 100000 #define db double int T, n, cnt; db ans, cal[maxn], sum[maxn], id[maxn]; struct node { db x1, x2, y1, y2; int id; node(db X1 = 0, db Y1 = 0, db X2 = 0, db Y2 = 0) { x1 = X1, y1 = Y1, x2 = X2, y2 = Y2; } friend bool operator <(const node& a, const node& b) { return a.x1 < b.x1; } }P[maxn], X[maxn]; struct node2 { int x1, x2, k; db h; node2(int X1 = 0, int X2 = 0, db H = 0, int K = 0) { x1 = X1, x2 = X2, h = H, k = K; } friend bool operator <(const node2& a, const node2& b) { return a.h < b.h; } }L[maxn]; void Update(int p, int l, int r, int L, int R, int x) { if(L <= l && R >= r) { cal[p] += x; if(cal[p]) sum[p] = id[r + 1] - id[l]; else sum[p] = sum[p << 1] + sum[p << 1 | 1]; return; } if(L > r || R < l) return; int mid = (l + r) >> 1; Update(p << 1, l, mid, L, R, x); Update(p << 1 | 1, mid + 1, r, L, R, x); if(cal[p]) sum[p] = id[r + 1] - id[l]; else sum[p] = sum[p << 1] + sum[p << 1 | 1]; } void init() { memset(sum, 0, sizeof(sum)); memset(cal, 0, sizeof(cal)); } int main() { while(scanf("%d", &n), n != 0) { int tot = 2 * n; init(); cnt = 0, ans = 0; for(int i = 1; i <= n; i ++) { db x1, x2, y1, y2; scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2); P[i] = node(x1, y1, x2, y2); X[i] = node(x1, 0, 0); X[i + n] = node(x2, 0, 1); X[i].id = X[i + n].id = i; } sort(X + 1, X + 1 + tot); X[0].x1 = -1; for(int i = 1; i <= tot; i ++) { if(X[i].x1 != X[i - 1].x1) id[++ cnt] = X[i].x1; if(!X[i].x2) P[X[i].id].x1 = cnt; else P[X[i].id].x2 = cnt; } for(int i = 1; i <= n; i ++) { L[i] = node2(P[i].x1, P[i].x2, P[i].y1, 1); L[i + n] = node2(P[i].x1, P[i].x2, P[i].y2, -1); } sort(L + 1, L + 1 + tot); for(int i = 1; i <= tot; i ++) { if(i != 1) ans += (L[i].h - L[i - 1].h) * sum[1]; Update(1, 1, cnt, L[i].x1, L[i].x2 - 1, L[i].k); } printf("Test case #%d\nTotal explored area: %.2f\n\n", ++ T, ans); } return 0; }
T2.洛谷P1502 窗口的星星
求在一个矩形中点权的最大值。我们可以发现一件事：将窗口的左下角位于一颗星星的地方一定是最优的。那么我们可以定义一颗星星的管辖范围为一个以它为左下角的，长为 \(W\)，宽为 \(H\) 的矩形。这样就拥有了一个很好的性质：如果两个矩形有交点，就说明这两个节点可以同时出现在窗口中。这样我们可以使用一条扫描线从左往右扫过整个平面，让线段树中存储的矩形均为左竖线与扫描线距离在 \(W\) 之内的矩形。接下来这其中的矩形均为可以水平相交的矩形，接下来只要用线段树解决竖直方向相交的问题了。我们在线段树上定义一个节点为可以覆盖到这个节点的所有矩形的权值之和，答案就是所有节点中的最大值。
#include <bits/stdc++.h> using namespace std; #define maxn 450000 #define int long long int n, W, H, mark[maxn], mx[maxn]; int tot, cnt, ans; int read() { int x = 0, k = 1; char c; c = getchar(); while(c < ‘0‘ || c > ‘9‘) { if(c == ‘-‘) k = -1; c = getchar(); } while(c >= ‘0‘ && c <= ‘9‘) x = x * 10 + c - ‘0‘, c = getchar(); return x * k; } struct node { int x, y, k; friend bool operator <(const node& a, const node& b) { return a.x == b.x ? a.y < b.y : a.x < b.x; } }P[maxn], X[maxn]; struct node2 { int l, r, h, k; node2(int L = 0, int H = 0, int K = 0) { l = L, h = H, k = K; } friend bool operator <(const node2& a, const node2& b) { return a.h == b.h ? a.k > b.k : a.h < b.h; } }L[maxn]; void Push_down(int p) { if(!mark[p]) return; mark[p << 1] += mark[p], mark[p << 1 | 1] += mark[p]; mx[p << 1] += mark[p], mx[p << 1 | 1] += mark[p]; mark[p] = 0; } void Update(int p, int l, int r, int L, int R, int k) { if(L <= l && R >= r) { mark[p] += k, mx[p] += k; return; } if(L > r || R < l) return; Push_down(p); int mid = (l + r) >> 1; Update(p << 1, l, mid, L, R, k); Update(p << 1 | 1, mid + 1, r, L, R, k); mx[p] = max(mx[p << 1], mx[p << 1 | 1]); } void init() { memset(mx, 0, sizeof(mx)); memset(mark, 0, sizeof(mark)); memset(L, 0, sizeof(L)); } signed main() { int T = read(); while(T --) { init(); ans = -1; n = read(), W = read(), H = read(); for(int i = 1; i <= n; i ++) { P[i].x = read(), P[i].y = read(), P[i].k = read(); X[i].x = P[i].x, X[i].k = i; X[i + n].x = P[i].x + W - 1, X[i + n].k = i; } tot = 2 * n, cnt = 0; sort(X + 1, X + 1 + tot); X[0].x = -1; for(int i = 1; i <= tot; i ++) { if(X[i].x != X[i - 1].x) cnt ++; if(!L[X[i].k].l) L[X[i].k] = node2(cnt, P[X[i].k].y, P[X[i].k].k); else L[X[i].k].r = cnt; } for(int i = 1; i <= n; i ++) { L[i + n] = L[i], L[i + n].k = -L[i].k; L[i + n].h = L[i].h + H - 1; } sort(L + 1, L + 1 + tot); for(int i = 1; i <= tot; i ++) { Update(1, 1, tot, L[i].l, L[i].r, L[i].k); ans = max(ans, mx[1]); } printf("%lld\n", ans); } return 0; }
【题解】HDU1542 Atlantis & 洛谷P1502 窗口的星星
原文：https://www.cnblogs.com/twilight-sx/p/9490939.html