线段树扫描线的模板题，一个月前写的发现忘了一些还是要看看以前的博客呀！
/* 思路：数据小不用离散化处理，线段树叶子结点维护一个区间 */ #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; #define maxn 20005 struct Seg{ int l,r,h,s; Seg(){} Seg(int a,int b,int c,int d):l(a),r(b),h(c),s(d){} bool operator<(const Seg & a)const { //if(h==a.h) return s>a.s; return h<a.h; } }ss[maxn]; bool lbd[maxn<<2],rbd[maxn<<2];//被覆盖的区域是否和左右区间线重合 int numseg[maxn<<2],cnt[maxn<<2],len[maxn<<2]; void pushup(int rt,int l,int r){ if(cnt[rt]){ lbd[rt]=rbd[rt]=1; len[rt]=r-l; numseg[rt]=2; } else if(l+1==r) len[rt]=numseg[rt]=rbd[rt]=lbd[rt]=0; else { lbd[rt]=lbd[rt<<1]; rbd[rt]=rbd[rt<<1|1]; len[rt]=len[rt<<1]+len[rt<<1|1]; numseg[rt]=numseg[rt<<1]+numseg[rt<<1|1]; if(lbd[rt<<1|1] && rbd[rt<<1]) numseg[rt]-=2; } } #define lson l,m,rt<<1 #define rson m,r,rt<<1|1 void update(int L,int R,int c,int l,int r,int rt){ if(L<=l && R>=r){ cnt[rt]+=c; pushup(rt,l,r); return; } int m=l+r>>1; if(L<m) update(L,R,c,lson); if(R>m) update(L,R,c,rson); pushup(rt,l,r); } void init(){ memset(lbd,0,sizeof lbd); memset(rbd,0,sizeof rbd); memset(cnt,0,sizeof cnt); memset(len,0,sizeof len); memset(numseg,0,sizeof numseg); } int main(){ int n; while(scanf("%d",&n)==1){ init(); int m=0,x1,y1,x2,y2,lbd=9999999,rbd=-9999999,last=0,ans=0; for(int i=1;i<=n;i++){ scanf("%d%d%d%d",&x1,&y1,&x2,&y2); ss[m++]=Seg(x1,x2,y1,1); ss[m++]=Seg(x1,x2,y2,-1); lbd=min(lbd,x1),rbd=max(rbd,x2); } sort(ss,ss+m); for(int i=0;i<m;i++){ update(ss[i].l,ss[i].r,ss[i].s,lbd,rbd,1); ans+=abs(len[1]-last);last=len[1]; ans+=numseg[1]*(ss[i+1].h-ss[i].h); } printf("%d\n",ans); } return 0; }
转载于:https://www.cnblogs.com/zsben991126/p/10061111.html
