20pts求助
查看原帖
20pts求助
244294
__Chtholly楼主2023/6/27 02:26
#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long 
const ll N=1e5+5;

ll n;
ll val[N<<2], tur[N<<2];
struct node{
	ll x,y1,y2,flag;
}a[N<<2];
struct edge{
	ll l,r,tag,sum;
}Tree[N<<4];

inline ll read(){
	ll x=0,f=1;
	char ch;
	while(ch=getchar()){
		if(ch>='0'&&ch<='9')break;
	}
	x=ch-'0';
	while(ch=getchar()){
		if(ch<'0'||ch>'9')break;	
		x=x*10+ch-'0';
	}
	return x;
}
void pushup(ll rt){
	ll x, y,l,r;
	x=rt<<1;
	y=rt<<1|1;
	l=Tree[rt].l;
	r=Tree[rt].r;
	if(Tree[rt].tag>0)
		Tree[rt].sum=tur[r+1]-tur[l];
	else
		Tree[rt].sum=Tree[x].sum+Tree[y].sum;
		
}
//void pushdown(ll rt){
//	ll x,y;
//	x=rt<<1;
//	y=rt<<1|1;
//	if(Tree[rt].tag){
//		Tree[x].tag=Tree[y].tag=Tree[rt].tag;
//		Tree[rt].tag=0;
//	}
//}
void build(ll l, ll r, ll rt){
	Tree[rt].l=l,Tree[rt].r=r;
	if(l==r)return ;
	ll m=(l+r)>>1;
	build(l,m,rt<<1);
	build(m+1,r,rt<<1|1);	
}
void update(ll rt, ll L, ll R, ll k){
	ll l,r;
	l=Tree[rt].l,r=Tree[rt].r;
	if(r<L||l>R)return ;
	if(L<=l&&r<=R){
		Tree[rt].tag+=k;
		pushup(rt);
		return ;
	}
	update(rt<<1,L,R,k);
	update(rt<<1|1,L,R,k);
	pushup(rt);
}
bool cmp(node a, node b){return a.x<b.x;}
int main(){
	freopen("P5490_3.in","r",stdin);
	freopen("5490.out","w",stdout);
	scanf("%lld",&n);
	for(ll i=1;i<=n;++i){
		ll xk1,xk2,yk1,yk2,pos1,pos2;
		xk1=read(),yk1=read(),xk2=read(),yk2=read();
		pos1=i*2-1;pos2=i*2;
		a[pos1].x=xk1,a[pos1].y1=yk1,a[pos1].y2=yk2,a[pos1].flag=1;
		a[pos2].x=xk2,a[pos2].y1=yk1,a[pos2].y2=yk2,a[pos2].flag=-1;
		val[pos1]=yk1,val[pos2]=yk2;
	}
	n*=2;
	sort(a+1,a+1+n,cmp);
	sort(val+1,val+1+n);
	int tot=unique(val+1,val+1+n)-val-1;
	for(ll i=1;i<=n;++i){
		ll pos1,pos2;
		pos1=lower_bound(val+1,val+1+n,a[i].y1)-val;
		pos2=lower_bound(val+1,val+1+n,a[i].y2)-val;
		tur[pos1]=a[i].y1;
		tur[pos2]=a[i].y2;
		a[i].y1=pos1;
		a[i].y2=pos2;
	}
	build(1,tot-1,1);
	ll ans=0;
	for(ll i=1;i<n;++i){
		update(1,a[i].y1,a[i].y2-1,a[i].flag);
		ans+=1ll*Tree[1].sum*(a[i+1].x-a[i].x);
//		printf("===%d\n",Tree[1].sum);
	}
	printf("%lld\n",ans);
	return 0;
}
2023/6/27 02:26
加载中...