扫描线
线段树的一大应用是扫描线。
扫描线一个很经典的例题：在坐标轴上有若干个矩形，问他们覆盖的面积总和。
扫描线求重叠矩形面积
思路
使用一条垂直于X轴的直线，从左到右来扫描这个图形，明显，只有在碰到矩形的左边界或者右边界的时候，这个线段所扫描到的情况才会改变。
所以把所有矩形的入边，出边按 X 值排序。然后根据 X 值从小到大去处理。
用线段树来维护扫描到的情况，即每条线段映射到 Y 轴上进行区间维护。
算法流程
一条垂直于 x 轴的直线，从左边向右平移
此时 y 轴上有一棵线段树，它记录的是 y 轴上每个点的覆盖次数
每当遇到某个矩形的某一条边时，就计算面积 —— （该边 x 坐标 – 上一边 x 坐标）* （当前整个 y 轴上被覆盖的点数）
当遇到某个矩形的左边，将这个矩形的左边所对应的y轴区间的覆盖次数 + 1。当遇到某个矩形的右边时，就相应的 − 1。
继续向右移动……
（注意，3操作要在4操作之前！）
性质
如何计算面积？
两条扫描线的间距很容易得到，重点是线段树部分的实现。
线段树操作：
区间修改（[L, R] + k）
区间查询（整个 y 轴上被覆盖次数大于 0 的点数）
在此可以发现这道题的两个性质：
对于询问，每次都查询的是根节点的信息，所以不需要query。
所有修改，都是成对出现，且对于每个区间一定是先执行 + 操作，在执行− 操作，即 cnt >= 0恒成立。
也就是说，相应的区间前后操作的都是线段树上完全相同的节点。（这很关键）
修改不需要pushdown的两种情况讨论：
cnt>0：
cnt=0：
本在pushdown中，add为0就不需要下传懒标记信息，等同于没pushdown。
又因为query函数没有，所以本题可以不用pushdown。
首先将所有矩形的入边，出边都存起来，然后根据 X 值排序。用结构体，来存这些信息，然后排序。
struct Line { double x, y1, y2; double d; // 表示+1 or -1 bool operator<(const Line &A) const { return x < A.x; } } line[N << 1];
- 线段树节点
struct node { int l, r; int cnt; // 重复包含次数 double len; // 当前节点维护的区间内部，有效的线段长度 } tr[N << 3];
pushup
void pushup(int u) { // 当前区间被覆盖，该段长度就为右端点 + 1后在ys中的值 - 左端点在ys中的值 if(tr[u].cnt) tr[u].len = ys[tr[u].r + 1] - ys[tr[u].l]; // 该段不被完全覆盖，那么清空该段的len值，而由可能存在其子区间段对len的贡献来更新 else if(tr[u].l != tr[u].r) tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len; // 叶子节点，len=0 else tr[u].len = 0; }
经典例题
247. 亚特兰蒂斯
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 100010; struct Line { double x, y1, y2; double d; bool operator<(const Line &A) const { return x < A.x; } } line[N << 1]; struct node { int l, r; int cnt; // 重复包含次数 double len; // 当前节点维护的区间内部，有效的线段长度 } tr[N << 3]; vector<double> ys; int n, t; int find(double x) { return lower_bound(ys.begin(), ys.end(), x) - ys.begin(); } void pushup(int u) { // 当前区间被覆盖，该段长度就为右端点 + 1后在ys中的值 - 左端点在ys中的值 if(tr[u].cnt) tr[u].len = ys[tr[u].r + 1] - ys[tr[u].l]; // 该段不被完全覆盖，那么清空该段的len值，而由可能存在其子区间段对len的贡献来更新 else if(tr[u].l != tr[u].r) tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len; // 叶子节点，len=0 else tr[u].len = 0; } 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); } // 线段树中 l点到r点出现次数 +k void modify(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 + tr[u].r >> 1; if(l <= mid) modify(u << 1, l, r, k); if(r > mid) modify(u << 1 | 1, l, r, k); pushup(u); } int main() { while(cin >> n, n) { ys.clear(); double x1, y1, x2, y2; int j = 0; for (int i = 0; i < n; i++) { cin >> x1 >> y1 >> x2 >> y2; line[j++] = {x1, y1, y2, 1}; line[j++] = {x2, y1, y2, -1}; ys.push_back(y1), ys.push_back(y2); } sort(line, line + j); sort(ys.begin(), ys.end()); ys.erase(unique(ys.begin(), ys.end()), ys.end()); build(1, 0, ys.size() - 2); double res = 0; for (int i = 0; i < j; i++) { if(i) res += tr[1].len * (line[i].x - line[i - 1].x); modify(1, find(line[i].y1), find(line[i].y2) - 1, line[i].d); } printf("Test case #%d\n", ++t); printf("Total explored area: %.2lf\n\n", res); } return 0; }
