20分,求助!!!
查看原帖
20分,求助!!!
544446
Demon_master楼主2022/2/22 15:31
#include<bits/stdc++.h>
using namespace std;
const long long maxn=1e5+21;

inline long long read_int(){
	long long x=0;bool f=0;char c=getchar();
	while (c<'0'||c>'9'){if (c=='-')f=1;c=getchar();}
	while (c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return f?-x:x;
}

long long n,l,X[maxn*2];
struct E{
	long long h,x1,x2,k;
	friend bool operator < (E a,E b){return a.h<b.h;}
}line[maxn*2];

struct TREE{
	long long cnt=0,len=0;
}tree[maxn*16];

inline void CCF_check(long long num,long long l,long long r){
	if(tree[num].cnt){
		tree[num].len=X[r+1]-X[l];
		return;
	}
	else tree[num].len=tree[num<<1|1].len+tree[num<<1].len;
	return;
}

void change(long long num,long long l,long long r,long long L,long long R,long long k){
	if(L<=l&&r<=R){
		tree[num].cnt+=k;
		CCF_check(num,l,r);
		return;
	}
	long long mid=(l+r)>>1;
	if(L<=mid) change(num<<1,l,mid,L,R,k);
	if(mid<R) change(num<<1|1,mid+1,r,L,R,k);
	CCF_check(num,l,r);
}

long long ans=0;

inline void read(){
	n=read_int();
	for(long long i=1;i<=n;i++){
		long long x1=read_int(),y1=read_int(),x2=read_int(),y2=read_int();
		l++,line[l]=(E){y1,x1,x2,1};
		X[l]=x1;
		l++,line[l]=(E){y2,x1,x2,-1};
		X[l]=x2;
	}
	sort(X+1,X+l+1);
	long long tot=unique(X+1,X+1+l)-X-1-1;
	sort(line+1,line+1+l);
	for(long long i=1;i<=l;i++) line[i]=(E){line[i].h,lower_bound(X+1,X+1+l,line[i].x1)-X,lower_bound(X+1,X+1+l,line[i].x2)-X-1,line[i].k};
//	for(int i=1;i<=l;i++) cout<<line[i].h<<" "<<line[i].k<<" "<<line[i].x1<<" "<<line[i].x2<<endl;
	for(long long i=1;i<l;i++){
		change(1,1,tot,line[i].x1,line[i].x2,line[i].k);
		ans+=tree[1].len*(line[i+1].h-line[i].h);
	}
	printf("%lld\n",ans);
}

int main (){
//	freopen("P5490.in","r",stdin);
	read();
}

2022/2/22 15:31
加载中...