扫描线 学习笔记

## 扫描线用来干什么 解决`二维平面`上的一些问题，如矩阵面积并 ~~不知应该归到DS还是计算几何~~ ## 扫描线主过程 以下是矩阵面积并。 先对 $x$, $y$ 分别进行离散化。 建线段树对 $y$ 轴当前被覆盖的区间长度进行维护。 将每个矩阵分裂成两个操作： 1. $(x_1,y_1,y_2,1)$ 2. $(x_2,y_1,y_2,-1)$ 对操作按 $x$ 值排序，依次执行如下 $\operatorname{change}$ 操作即可。 - $\operatorname{change}(x_1,y_1,y_2,1)$ - $\operatorname{change}(x_2,y_1,y_2,-1)$ 然后每次 $\operatorname{change}$ 完，在 $ans$ 中累加 $\operatorname{query}()$ 的值。 其中 $\operatorname{query}()$ 代表当前被覆盖的长度，即代码中的 `siz(1)`。 还有，因为增操作和减操作一 一对应，所以不用下传 `lazy_tag`。 ## 特别注意 **空间一定要开大！！！** 离散化、询问数组各开 **2** 倍； 线段树数组开 **16** 倍！（因为会多次越界访问） 如果卡空间可以加**亿些**判断。 ## 模板 - [P5490 【模板】扫描线](https://www.luogu.com.cn/problem/P5490) Code： ```cpp #include<bits/stdc++.h> using namespace std; #define fo(v,a,b) for(int v=a;v<=b;v++) #define fo2(v,a,b) for(v=a;v<=b;v++) #define fr(v,a,b) for(int v=a;v>=b;v--) #define rg register #define il inline typedef long long ll; const int N=100010; int n,x1[N],y3[N],x2[N],y2[N]; int x[N<<1],totx,y[N<<1],toty; map<int,int> mx,my; struct Segment_Tree { struct node { int l,r; int t; ll len,Len; #define l(x) a[x].l #define r(x) a[x].r #define t(x) a[x].t #define len(x) a[x].len #define Len(x) a[x].Len }a[1600010]; void build(int p,int l,int r) { if(l>r)return ; l(p)=l,r(p)=r,t(p)=len(p)=0; Len(p)=y[r]-y[l-1]; if(l==r)return ; int mid=(l+r)>>1; build(p<<1,l,mid);build(p<<1|1,mid+1,r); len(p)=0; } void update(int p) { if(t(p))len(p)=Len(p); else len(p)=len(p<<1)+len(p<<1|1); } void change(int p,int l,int r,int c) { if(l<=l(p)&&r(p)<=r) { t(p)+=c;update(p);return ; } int mid=(l(p)+r(p))>>1; if(l<=mid)change(p<<1,l,r,c); if(mid<r)change(p<<1|1,l,r,c); update(p); } il ll query() { return len(1); } }T; struct query { int x; int y1,y2; int c; }q[400010];int qtot=0; void read() { cin>>n; fo(i,1,n) { scanf("%d%d%d%d",&x1[i],&y3[i],&x2[i],&y2[i]); x[++totx]=x1[i],x[++totx]=x2[i]; y[++toty]=y3[i],y[++toty]=y2[i]; } sort(x+1,x+totx+1); sort(y+1,y+toty+1); totx=unique(x+1,x+totx+1)-(x+1); toty=unique(y+1,y+toty+1)-(y+1); fo(i,1,totx)mx[x[i]]=i; fo(i,1,toty)my[y[i]]=i; fo(i,1,n) { x1[i]=mx[x1[i]],x2[i]=mx[x2[i]]; y3[i]=my[y3[i]],y2[i]=my[y2[i]]; } } ll ans=0LL; bool cmp(query C,query D) { return C.x<D.x; } int main() { read(); fo(i,1,n) { q[++qtot].x=x1[i],q[qtot].c=1; q[qtot].y1=y3[i]+1,q[qtot].y2=y2[i]; q[++qtot].x=x2[i],q[qtot].c=-1; q[qtot].y1=y3[i]+1,q[qtot].y2=y2[i]; } sort(q+1,q+qtot+1,cmp); T.build(1,2,toty);//i->y[i-1]~y[i] q[qtot+1].x=q[qtot].x; fo(i,1,qtot) { T.change(1,q[i].y1,q[i].y2,q[i].c); ans+=T.query()*(x[q[i+1].x]-x[q[i].x]); } printf("%lld\n",ans); return 0; } ```