题解 P5490 【【模板】扫描线】
本题解主要是为了想要学习扫描线算法的同学准备的。
在开始学习本算法前，你需要会：
-
线段树
-
离散化
没了……
切入正题
本题给出了n个矩形，求出它们在平面上覆盖的面积。
然后我们开始思考……
首先，
于是
所以然后咋办？？？
1. 暴力for循环？
憋想了，MLE+TLE
2. 容斥定理？
没学过没关系，反正是错的
把所有的矩形面积相加，然后减去重叠部分？
憋想了，烦死你
那咋办
（敲黑板）正解来啦！！！
3. 分割图形？
比如……
好像可行！
but具体怎么操作呢？
看到最后一步图片的虚线了吗？
所以……
是不是有一点想法了呢？
然后我们再来模拟一波……
答案是不是呼之欲出了呢！
我们记录每一条竖直方向上的线段（一个含x坐标，上端y坐标y1，下端y坐标y2，加减的标记k的四元组(x,y1,y2,k)）然后离散化(得到离散化后的值val(y)，离散化值对应的y值raw(i))，按照x坐标进行排序；
变成这样↓
然后维护扫描线上被覆盖的长度就好了！！！
最后……如何维护这条扫描线呢？
线段树横空出世！
每次修改之后，更新线段树中节点的len(被覆盖的长度)
相信会线段树的同学都能独立完成所以就不贴代码了
至此，本题已经 基本上 解决了！
为什么说是基本上呢？当然是还有优化啦~
（这才是你上面不贴代码的原因吧！！！）
（好好好下面我绝对贴……）
区间修改的延时标记太麻烦了……算了不写了
且慢！这题还有不用延时标记的优化！
话说延时标记……
是一种 使区间修改不用全部下传至叶子节点，在查询子节点的值时才下传，从而保证在
查询子节点的值？？？
我们不是只查询全图最低点到最高点的值，也就是，根节点的值吗？
那管儿子节点的事干嘛，让他们自生自灭得了
于是，我们想到，除左右端点l,r之外，在线段树的每个节点上维护两个值：该节点代表的区间被矩形覆盖的长度len，该节点自身被覆盖的次数cnt。最初，二者均为0.
对于每一个(x,y1,y2,k)，我们再[val(y1),val(y2)-1]上执行期间修改。该区间被线段树划分成
对于线段树中任意一个节点 [l,r] ，若cnt>0，则len等于raw(r+1)-raw(l),否则，该店len等于两个子节点的len之和。在一个节点的cnt被修改，以及线段树从下往上传递信息时，我们都按照该方法更新len值。根节点的len值就是整个扫描线上被覆盖的长度
——from 《算法竞赛进阶指南》
到这里这篇题解也就完美结束了……
是不是忘了些什么
code time:
#include<bits/stdc++.h>
using namespace std;
#define ls (rt << 1)//左儿子
#define rs (rt << 1 | 1)//右儿子
#define int long long
int n, x_, x__, y_, y__, x, y, rk[2097152], val[2097152], cnt, maxn = 1 << 31;
//注意：用万能库的同学千万不要以x1,x2,y1,y2作为变量名!!!!!!
//maxn是为了保证不会去理左右端点
struct Segment_tree
{
int l, r;//区间左右端点
int cnt, len;//如上所述
}t[2097152];
struct node
{
int x, yh, yl, flag;
}e[2097152];//记录每一条竖线
void pushup(int rt)
{
if ((t[rt].l == maxn && t[rt].r == maxn)) return;
if (t[rt].cnt) t[rt].len = val[t[rt].r + 1] - val[t[rt].l];
else t[rt].len = t[ls].len + t[rs].len;
}//向上更新节点
void build(int rt, int l, int r)
{
t[rt].l = l, t[rt].r = r;
if (l == r) return;
int mid = (t[rt].l + t[rt].r) >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
}
void add(int rt, int l, int r, int v)
{
if (l <= t[rt].l && t[rt].r <= r)
{
t[rt].cnt += v;
pushup(rt);
return;
}
int mid = (t[rt].l + t[rt].r) >> 1;
if (l <= mid) add(ls, l, r, v);
if (mid < r) add(rs, l, r, v);
pushup(rt);
}//基本操作，不再赘述
bool cmp(node a, node b)
{
if (a.x != b.x) return a.x < b.x;
return a.flag > b.flag;
}
signed main()
{
cin >> n;
int ans = 0;
for (int i = 1; i <= n; i++)
{
scanf("%lld%lld%lld%lld", &x_, &y_, &x__, &y__);
e[(i << 1) - 1].x = x_, e[i << 1].x = x__;
e[(i << 1) - 1].yh = e[i << 1].yh = y__;
e[(i << 1) - 1].yl = e[i << 1].yl = y_;
e[(i << 1) - 1].flag = 1, e[i << 1].flag = -1;//flag表示该边是矩形的左边界或右边界
rk[++cnt] = y_;
rk[++cnt] = y__;//存入一个数组，准备离散化
}
sort(rk + 1, rk + (n << 1) + 1);//排序
cnt = unique(rk + 1, rk + (n << 1) + 1) - rk - 1;//去重
for (int i = 1; i <= 2 * n; i++)
{
int pos1 = lower_bound(rk + 1, rk + cnt + 1, e[i].yh) - rk;
int pos2 = lower_bound(rk + 1, rk + cnt + 1, e[i].yl) - rk;//在数组中二分查找位置
val[pos1] = e[i].yh;
val[pos2] = e[i].yl;//即为上文的raw数组
e[i].yh = pos1; maxn = max(maxn, pos1);
e[i].yl = pos2;
}
sort(e + 1, e + 2 * n + 1, cmp);//按照x坐标
build(1, 1, n << 1);
for (int i = 1; i < n << 1; i++)
{
add(1, e[i].yl, e[i].yh - 1, e[i].flag);//区间加flag
ans += t[1].len * (e[i + 1].x - e[i].x);//根节点的len值*与下一条线段的距离=这一块内的矩形面积
}
cout << ans << endl;//得到最终答案,AC!
return 0;
}