之前并不能理解扫描线这种东西，真的以为是条线，还在想这玩意到底要怎么实现？
结果理解后，好像还真是条线。
好吧。其实是以一个坐标轴的点确定的直线+长度，直线和长度便确定了线段，也有了值。
扫描线应该说是靠顺序查询轴线点来实现的。
看了一个大佬的博客，受益匪浅。我是看了这个博客才明白扫描线这东西的做法。
然后根据那个博客，我改了里边的代码，做了我扫描线的第一题，洛谷的P1904：
#include<bits/stdc++.h> using namespace std; const int maxn=5e4+50; int mark[maxn<<2];//记录某个区间的下底边个数 int sum[maxn<<2];//记录某个区间的下底边总长度 int a[maxn];//对h进行离散化 //以纵坐标作为线段(区间)，对纵坐标线段进行扫描 struct P{ int x,h,ju;//以h为扫描线平行边，x为扫描方向，ju=-1为左 ju=1为右 bool operator <(const P&p)const{return x<p.x;} P(){} P(int xx,int hh,int juu){x=xx;h=hh;ju=juu;} }s[maxn]; void upfather(int k,int l,int r){ if(mark[k])sum[k]=a[r+1]-a[l];// else if(l==r)sum[k]=0; else sum[k]=sum[k<<1]+sum[k<<1|1]; }//n k void update(int L,int R,int ju,int k,int l,int r){ if(L<=l&&r<=R){ mark[k]+=ju; upfather(k,l,r); return; } int mid=(l+r)>>1; if(L<=mid)update(L,R,ju,k<<1,l,mid); if(R>mid)update(L,R,ju,k<<1|1,mid+1,r); upfather(k,l,r); } int search(int key,int *x,int k){ int l=0,r=k-1; while(l<=r){ int mid=(l+r)>>1; if(x[mid]==key)return mid; if(x[mid]>key)r=mid-1; else l=mid+1; } return -1; } struct PP{ int x,y; PP(){} PP(int xx,int yy){x=xx;y=yy;} }ans[maxn<<2]; int solve(int tot,int up)//tot是边数 up是点数 { int upp=0,tans=0; for(int i=0;i<tot;i++){ int R=search(s[i].h,a,up)-1; update(0,R,s[i].ju,1,0,up-1);//printf("!"); if(sum[1]==tans)continue; if(ans[upp-1].x==s[i].x&&ans[upp-1].y==tans)upp--; else ans[upp++]=PP(s[i].x,tans); if(ans[upp-1].x==s[i].x&&ans[upp-1].y==sum[1])upp--; else ans[upp++]=PP(s[i].x,sum[1]); tans=sum[1]; } return upp; } int main() { int n,tot=0,l,h,r,up=0; a[up++]=0; // scanf("%d",&n); while(~scanf("%d%d%d",&l,&h,&r)) // while(tot<n*2) { // scanf("%d%d%d",&l,&h,&r); a[up++]=h; s[tot++]=P(l,h,-1); s[tot++]=P(r,h,1); } sort(a,a+up); sort(s,s+tot); up=unique(a,a+up)-a; int upp=solve(tot,up); for(int i=0;i<upp;i++) { if(i&1)printf("%d ",ans[i].y); else printf("%d ",ans[i].x); // printf("%d% d\n",ans[i].x,ans[i].y); } }
2019-09-04
原文：https://www.cnblogs.com/kkkek/p/11462426.html