那看似平凡的面積，是多少條線的織物啊

前言

突然發(fā)現(xiàn)自己之前沒發(fā)過掃描線的模板
可能是因為之前的實現(xiàn)太差了
這次感覺實現(xiàn)的還是很不錯的，
雖然常數(shù)比較大，但是好寫啊！
原來掃描線也是可以1A的

線段樹上利用zld講解的維護最小值和最小值數(shù)量的方法輕松維護
離散化后邊化點的細節(jié)現(xiàn)在看其實也沒有那么難了

代碼

#include<bits/stdc++.h>const int N=4e5+100; const int M=50050; const int mod=1e9+7; #define ll long long #define ull unsigned long long #define debug(...) fprintf(stderr,__VA_ARGS__) using namespace std; inline ll read() {ll x(0),f(1);char c=getchar();while(!isdigit(c)) {if(c=='-')f=-1;c=getchar();}while(isdigit(c)) {x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; }int n,m; int q[N],num; int x1[N],yy1[N],x2[N],y2[N]; struct ope{int h,l,r,op;bool operator < (const ope o)const{return h<o.h;} }o[N]; int tot;#define mid ((l+r)>>1) #define ls (k<<1) #define rs (k<<1|1) int mn[N<<2],sum[N<<2],laz[N<<2]; inline void pushup(int k){mn[k]=min(mn[ls],mn[rs]);sum[k]=0;if(mn[k]==mn[ls]) sum[k]+=sum[ls];if(mn[k]==mn[rs]) sum[k]+=sum[rs];return; } inline void add(int k,int v){laz[k]+=v;mn[k]+=v;return; } inline void pushdown(int k){int o=laz[k];laz[k]=0;if(!o) return;add(ls,o);add(rs,o);return; } void build(int k,int l,int r){if(l==r){mn[k]=0;sum[k]=q[l+1]-q[l];return;}build(ls,l,mid);build(rs,mid+1,r);pushup(k);return; } void change(int k,int l,int r,int x,int y,int op){if(x<=l&&r<=y){add(k,op);return;}pushdown(k);if(x<=mid) change(ls,l,mid,x,y,op);if(y>mid) change(rs,mid+1,r,x,y,op);pushup(k);return; }int main(){ #ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout); #endifn=read();for(int i=1;i<=n;i++){q[++num]=x1[i]=read();q[++num]=yy1[i]=read();q[++num]=x2[i]=read();q[++num]=y2[i]=read();}sort(q+1,q+1+num);num=unique(q+1,q+1+num)-q-1;for(int i=1;i<=n;i++){x1[i]=lower_bound(q+1,q+1+num,x1[i])-q;yy1[i]=lower_bound(q+1,q+1+num,yy1[i])-q;x2[i]=lower_bound(q+1,q+1+num,x2[i])-q;y2[i]=lower_bound(q+1,q+1+num,y2[i])-q;o[++tot]=(ope){yy1[i],x1[i],x2[i]-1,1};o[++tot]=(ope){y2[i],x1[i],x2[i]-1,-1};}q[num+1]=q[num];build(1,1,num);sort(o+1,o+1+tot);ll ans(0);int pl=1;for(int i=1;i<num;i++){while(pl<=tot&&o[pl].h==i){change(1,1,num,o[pl].l,o[pl].r,o[pl].op);++pl;}ll add=q[num+1]-q[1]-(mn[1]?0:sum[1]);ans+=add*(q[i+1]-q[i]);}printf("%lld\n",ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的模板：扫描线的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。