链接：Miku
----------------------------
和HDu的那道还是蛮相似的，但是数据更强
---------------------------
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> using namespace std; int xx,yy,xxx,yyy; long long ans; const int maxn=100000; int last; struct li{ int l; int r; long long h; int f; }line[200005]; int n; int p; int sum[4000005]; bool ld[4000005],rd[4000005]; int lazy[4000005]; int summ[4000005]; int lm; int rm; bool cmp(li x,li y){ if(x.h==y.h) return x.f>y.f; return x.h<y.h; } void pushup(int x,int l,int r){ if(lazy[x]>=1){ sum[x]=r-l+1; summ[x]=2; ld[x]=rd[x]=1; } else if(l!=r){ sum[x]=sum[x<<1]+sum[x<<1|1]; ld[x]=ld[x<<1]; rd[x]=rd[x<<1|1]; summ[x]=summ[x<<1]+summ[x<<1|1]; if(ld[x<<1|1]&&rd[x<<1]) summ[x]-=2; } else{ sum[x]=0; summ[x]=0; ld[x]=0; rd[x]=0; } } void update(int x,int l,int r,int L,int R,int d){ if(L<=l&&r<=R){ lazy[x]+=d; pushup(x,l,r); return ; } //pushdown(x,l,r); int mid=(l+r)>>1; if(L<=mid) update(x<<1,l,mid,L,R,d); if(R>mid) update(x<<1|1,mid+1,r,L,R,d); pushup(x,l,r); } int main(){ while(~scanf("%d",&n)){ p=0; ans=0; last=0; lm=-10000; rm=10000; for(int i=1;i<=n;++i){ scanf("%d%d%d%d",&xx,&yy,&xxx,&yyy); //xx+=maxn; // xxx+=maxn; // yy+=maxn; // yyy+=maxn; lm=min(lm,xx); rm=max(rm,xxx); p++; line[p].l=xx; line[p].r=xxx; line[p].h=yy; line[p].f=1; p++; line[p].l=xx; line[p].r=xxx; line[p].h=yyy; line[p].f=-1; } sort(line+1,line+p+1,cmp); for(int i=1;i<=p;++i){ // if(line[i].l<line[i].r) update(1,lm,rm-1,line[i].l,line[i].r-1,line[i].f); ans+=summ[1]*(line[i+1].h-line[i].h); ans+=abs(sum[1]-last); last=sum[1]; // cout<<ans<<endl; } cout<<ans<<endl; } return 0; }