扫描线算是线段树的一个比较特殊的用法，虽然NOIP不一定会考，但是学学还是有用的，况且也不是很难理解。
以前学过一点，不是很透，今天算是搞懂了。
就以这道题为例吧：嘟嘟嘟
题目的意思是在一个二维坐标系中给了很多矩形，然后求这些矩形的总覆盖面积，也就是面积并。
我就不讲暴力，直接切入正题吧。
扫描线，听这个名字就可以想象一下，现在有这么多重叠的矩形，然后有一个线从下往上扫，那么每一时刻这条线上被覆盖的长度之和，就是我们要求的答案。
那么首先可以想到，要把给定的矩形都离线下来，拆成上下来个面，并标记这个矩形从哪开始，从哪结束，最后按x（或y）排好序。
上面的可以算作预处理，接下来才是重点：怎么用线段树维护这个扫描线的覆盖问题？
首先要清楚的是，这并不是单纯的区间覆盖，因为区间覆盖的清空是把这个区间都清零，但是在对于扫线上的一段区间的清空，实际上只是清空了这一层，而他下面那一层应该还保持原样。这该怎么实现呢？
首先需要一个cov标记，表示这个区间被覆盖了几层，那么一个矩形的开始就是多覆盖一层，结束就是减去一层。由此可知，如果cov > 1的话，那么这个区间就全被覆盖了，sum就等于区间长度；那么cov = 0呢？说明这个区间只有一部分被覆盖，sum[now] = sum[now <<1] +sum[now <<1 | 1]。这是为什么就等于左右子区间的和呢？想一下，我们更新的时候，要是更新区间和当前区间一样的话，就停止了，那么他的子区间还是保持了原来的情况。因此我们掀开了这一层，露出来的就是他的子区间那没有被完全覆盖的情况。因此sum[now] = sum[now << 1] +sum[now <<1 | 1].
还有一点，那就是cov永远不会小于0，因为cov--的条件是有一个矩形结束了，那有结束必定有开始，所以一定是先加后减。但有人又会问，如果是别的矩形改变了这个区间的cov值呢？那也同理，也是先加后减。所以cov永远是大于0的。
pushup也一样，cov大于0，则sum就是区间长度，否则是左右子区间的和。
（懒得画图……）
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define rg register
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-;
const int maxn = 5e4 + ;
inline ll read()
{
ll ans = ;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) {last = ch; ch = getchar();}
while(isdigit(ch)) {ans = ans * + ch - ''; ch = getchar();}
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < ) x = -x, putchar('-');
if(x >= ) write(x / );
putchar(x % + '');
} int xl, yl, xr, yr, cnt = ;
struct Node
{
int L, R, h, flg;
bool operator < (const Node &oth)const
{
return h < oth.h;
}
}a[maxn << ]; int l[maxn << ], r[maxn << ], sum[maxn << ], cov[maxn << ];
void build(int L, int R, int now)
{
sum[now] = cov[now] = ;
l[now] = L; r[now] = R;
if(L == R) return;
int mid = (L + R) >> ;
build(L, mid, now << );
build(mid + , R, now << | );
}
void update(int L, int R, int flg, int now)
{
if(L == l[now] && R == r[now])
{
cov[now] += flg;
if(cov[now]) sum[now] = R - L + ;
else
{
if(L == R) sum[now] = ; //别忘判断叶子节点
else sum[now] = sum[now << ] + sum[now << | ];
}
return;
}
int mid = (l[now] + r[now]) >> ;
if(R <= mid) update(L, R, flg, now << );
else if(L > mid) update(L, R, flg, now << | );
else update(L, mid, flg, now << ), update(mid + , R, flg, now << | );
if(cov[now]) sum[now] = r[now] - l[now] + ;
else sum[now] = sum[now << ] + sum[now << | ];
} int solve()
{
build(, maxn - , );
ll ans = ;
sort(a + , a + cnt + );
for(int i = ; i <= cnt; ++i)
{
update(a[i].L, a[i].R, a[i].flg, );
ans += sum[] * (a[i + ].h - a[i].h);
}
return ans;
} int main()
{
while()
{
cnt = ;
bool flg = ;
while()
{
xl = read() + ; yl = read() + ; xr = read(); yr = read() + ;
if(!xl && !flg) return ;
else if(!xl) break;
else
{
a[++cnt] = (Node){xl, xr, yl, };
a[++cnt] = (Node){xl, xr, yr, -};
flg = ;
}
}
write(solve()); enter;
}
return ;
}