线段树板子只有10pts求调qwq
查看原帖
线段树板子只有10pts求调qwq
682028
_awa_keyai楼主2023/8/15 11:27
//扫描线
#include<bits/stdc++.h>

using namespace std;

inline long long read(){
  long long ret=0,f=1;
  char c=getchar();
  for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-f;
  for(;c>='0'&&c<='9';c=getchar()) ret=ret*10+c-'0';
  return ret*f;
}

#define ls i<<1,l,m
#define rs i<<1|1,m+1,r

const long long maxn=1e6+55;
long long x[maxn*8];
struct awa{
	long long l,r,h;
	long long d;
	 awa (){}
	awa(long long l,long long r,long long h,long long d):l(l),r(r),h(h),d(d) {}
	bool operator < (const awa &a)const
	{
		return h<a.h;
	}
}line[maxn];

long long cnt[maxn*8];
double sum[maxn*8];

void pushup(long long i,long long l,long long r){
	if(cnt[i]){
		sum[i]=x[r+1]-x[l];
	} else {
		sum[i]=sum[i<<1]+sum[i<<1|1];
	}
}

void _update(long long al,long long ar,long long v,long long i,long long l,long long r){
	if(al<=l&&ar>=r){
		cnt[i]+=v;
		pushup(i,l,r);
		return;
	}
	long long m=(l+r)>>1;
	if(al<=m){
		_update(al,ar,v,ls);
	}
	if(ar>m){
		_update(al,ar,v,rs);
	}
	pushup(i,l,r);
}

signed main(void){

		long long n=0,m=0,q;
		cin>>q;
		for(long long i=1;i<=q;i++){
			long long x1,x2,y1,y2;
			scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
			x[++n]=x1;
			x[++n]=x2;
			line[++m]=awa(x1,x2,y1,1);
			line[++m]=awa(x1,x2,y2,-1);
		}
		sort(x+1,x+1+n);
		sort(line+1,line+1+m);
		long long k=1;
		k=unique(x+1,x+n+1)-x-1;
		long long ans=0;
		for(long long i=1;i<=m;i++){
			long long l=lower_bound(x+1,x+k+1,line[i].l)-x;
			long long r=lower_bound(x+1,x+k+1,line[i].r)-x-1;
			if(l<=r){
				_update(l,r,line[i].d,1,1,k-1);
			}
			ans+=sum[1]*(line[i+1].h-line[i].h);
		}
		printf("%lld",ans);

  return 0;
}
2023/8/15 11:27
加载中...