今天初步的学习了一下有关扫描线的相关知识。由于本人的做题量还不够大，理解也并不很深刻，所以这篇文章还是留给自己看吧~ 扫描线，顾名思义就是用一根线在一个平面上扫描，扫到线段 / 矩形的时候就将其所含有的信息从数据结构中删去 / 加入数据结构。
通过这几道题目，可以大致的感受到扫描线的作用与神奇之处。
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 Total explored area: %.2f ", ++ 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 ", ans); } return 0; }
T3.51nod1559 车和矩形
想了一个晚上的题……首先应该要发现一个性质：一个矩形要想被保护的话，必须满足所有行 / 所有列上均有一个车的限制。这样我们解决问题就可以转化为判断一个矩形所有行上是否都有一个车了（对于列只需要把图转一下做就可以）。这样我们自然想到线段树 + 扫描线，我是用列上的扫描线从上到下，每一次扫到一个矩形的下边界就判断一下。线段树上维护每一列上距离最远的一个车的纵坐标，我们判断一个矩形是否被保护就只需要判断最远的车是否在当前矩形的范围内了。感觉OFN说的扫描线就是把问题转化到一个前缀的维护上面去其实是挺有道理的恩~
#include <bits/stdc++.h> using namespace std; #define maxn 600000 #define INF 99999999 int n, m, K, Q, mx[maxn], ans[maxn]; 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; friend bool operator <(const node& a, const node& b) { return a.y > b.y; } }P[maxn]; struct square { int x1, y1, x2, y2, id; square(int a = 0, int b = 0, int c = 0, int d = 0, int e = 0) { x1 = a, y1 = b, x2 = c, y2 = d, id = e; } friend bool operator <(const square& a, const square& b) { return a.y1 > b.y1; } }S[maxn]; void Update(int p, int l, int r, int x, int y) { if(l == r) { mx[p] = y; return; } int mid = (l + r) >> 1; if(x <= mid) Update(p << 1, l, mid, x, y); else Update(p << 1 | 1, mid + 1, r, x, y); mx[p] = max(mx[p << 1], mx[p << 1 | 1]); } int Query(int p, int l, int r, int L, int R) { if(L <= l && R >= r) return mx[p]; if(L > r || R < l) return 0; int mid = (l + r) >> 1; return max(Query(p << 1, l, mid, L, R), Query(p << 1 | 1, mid + 1, r, L, R)); } void Work() { sort(P + 1, P + 1 + K); sort(S + 1, S + 1 + Q); for(int i = 1; i < maxn; i ++) mx[i] = INF; for(int i = 1, now = 1; i <= Q; i ++) { while(now <= K && P[now].y >= S[i].y1) Update(1, 1, n, P[now].x, P[now].y), now ++; int t = Query(1, 1, n, S[i].x1, S[i].x2); if(t <= S[i].y2 && t) ans[S[i].id] = 1; } } int main() { n = read(), m = read(), K = read(), Q = read(); for(int i = 1; i <= K; i ++) P[i].x = read(), P[i].y = read(); for(int i = 1; i <= Q; i ++) { int x1 = read(), y1 = read(), x2 = read(), y2 = read(); S[i] = square(x1, y1, x2, y2, i); } Work(); for(int i = 1; i <= K; i ++) swap(P[i].x, P[i].y); for(int i = 1; i <= Q; i ++) swap(S[i].x1, S[i].y1), swap(S[i].x2, S[i].y2); swap(n, m); Work(); for(int i = 1; i <= Q; i ++) if(ans[i]) puts("YES"); else puts("NO"); return 0; }
T4.七彩瀑布下的愿望花环
自己为机房欢乐赛出的一道水题hhh
题解：
#include <bits/stdc++.h> using namespace std; #define maxn 2000000 #define INF 9999999 #define int long long int n, K, ans = -INF, val[maxn], C[maxn]; int mark[maxn], mx[maxn]; int rec[maxn], last[maxn]; 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; } void Push_down(int p) { if(!mark[p]) return; mx[p << 1] += mark[p]; mx[p << 1 | 1] += mark[p]; mark[p << 1] += mark[p], mark[p << 1 | 1] += mark[p]; mark[p] = 0; } void Update(int p, int l, int r, int L, int R, int x) { if(L <= l && r <= R) { mark[p] += x; mx[p] += x; return; } if(L > r || R < l) return; Push_down(p); int mid = (l + r) >> 1; Update(p << 1, l, mid, L, R, x), Update(p << 1 | 1, mid + 1, r, L, R, x); mx[p] = max(mx[p << 1], mx[p << 1 | 1]); } signed main() { freopen("in.in", "r", stdin); n = read(), K = read(); for(int i = 1; i <= n; i ++) { val[i] = read(), C[i] = read(); rec[i] = last[C[i]]; last[C[i]] = i; } for(int i = 1; i <= n; i ++) { if(rec[i]) Update(1, 1, n, 1, rec[i], val[i]); Update(1, 1, n, rec[i] + 1, i, val[i] + K); ans = max(ans, mx[1]); } printf("%lld ", ans); return 0; }