萌新求助·
查看原帖
萌新求助·
115857
too_later楼主2020/10/29 13:55

是真的萌新。3AC7WA

#include<bits/stdc++.h>
#define I inline
#define int long long
#define RI int
#define CI const int&
#define N 200005
using namespace std;

struct line{ int x1,x2,y,val; bool operator <(const line &a1)const{return y<a1.y; }; } lne[N<<1];
struct tree{ int l,r,sum,len; tree(){ sum=len=0; } } tr[N<<2];

int n,x,xx,y,yy,tot,X[N<<1];

I void up(int p){ tr[p].len=tr[p].sum?X[tr[p].r+1]-X[tr[p].l]:tr[p<<1].len+tr[p<<1|1].len; }
I void build(int l,int r,int p){ tr[p].l=l,tr[p].r=r;if(l==r)return;RI mid=l+r>>1;build(l,mid,p<<1),build(mid+1,r,p<<1|1); }
I void update(int l,int r,int p,int c){
//	cout<<l<<' '<<r<<' '<<tr[p].l<<' '<<tr[p].r<<' '<<X[tr[p].l]<<' '<<X[tr[p].r+1]<<endl;
	if(X[tr[p].l]>=l&&X[tr[p].r+1]<=r){tr[p].sum+=c;up(p);return;}if(X[tr[p].l]>=r||X[tr[p].r+1]<=l)return;
	RI mid=tr[p].l+tr[p].r>>1;if(r<=X[mid+1])update(l,r,p<<1,c);else if(l>X[mid])update(l,r,p<<1|1,c);
	else update(l,X[mid+1],p<<1,c),update(X[mid+1],r,p<<1|1,c);up(p); }

signed main(){
	RI i;for(scanf("%lld",&n),i=1;i<=n;i++)scanf("%lld%lld%lld%lld",&x,&y,&xx,&yy),
		lne[i<<1]=line{x,xx,y,1},lne[(i<<1)-1]=line{x,xx,yy,-1},X[i<<1]=x,X[(i<<1)-1]=xx;
	sort(lne+1,lne+n*2+1);sort(X+1,X+2*n+1);tot=unique(X+1,X+n*2+1)-X-1;build(1,tot-1,1);
	int ans=0;for(i=1;i<n*2;i++){update(lne[i].x1,lne[i].x2,1,lne[i].val),ans+=(lne[i+1].y-lne[i].y)*tr[1].len; }
	return printf("%lld\n",ans),0;
}
2020/10/29 13:55
加载中...