20求调
  • 板块学术版
  • 楼主_lijianqiao_
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/9/26 20:22
  • 上次更新2023/11/2 17:58:52
查看原帖
20求调
1028513
_lijianqiao_楼主2023/9/26 20:22
#include<bits/stdc++.h>
using namespace std;
#define int long long

int x1,x2,yi,y2,n,ans;

struct sc{
	int x1,x2,y,c;
}line[200005];

int xx[200005];

struct node{
	int l,r,hl,hr,len,tag,rlen;
}tree[800005];

bool cmp(sc xx,sc yy){
	return xx.y<yy.y;
}

void build(int rt,int l,int r){
	tree[rt].l=l;tree[rt].r=r;
	if(l==r){tree[rt].hl=xx[l];tree[rt].hr=xx[r+1];tree[rt].len=xx[r+1]-xx[l];return;}
	int mid=(l+r)>>1;
	build(rt*2,l,mid);build(rt*2+1,mid+1,r);
	tree[rt].hl=tree[rt*2].hl;
	tree[rt].hr=tree[rt*2+1].hr;
	tree[rt].len=tree[rt*2].len+tree[rt*2+1].len;
}

void update(int rt,int l,int r,int hh){	
	if(tree[rt].l>=l&&tree[rt].r<=r){
		if(tree[rt].l==tree[rt].r){
			if(hh==1)tree[rt].tag++;
		    else if(hh==2)tree[rt].tag--;
			if(tree[rt].tag>0)tree[rt].rlen=tree[rt].len;
			else if(tree[rt].tag==0)tree[rt].rlen=0;
			return;
		}
	    if(hh==1)tree[rt].tag++;
	    else if(hh==2)tree[rt].tag--;
	    if(tree[rt].tag>0)tree[rt].rlen=tree[rt].len;
	    else if(tree[rt].tag==0){
	    	tree[rt].rlen=tree[rt*2].rlen+tree[rt*2+1].rlen;
		}
	    return;
	}
	int mid=(tree[rt].l+tree[rt].r)>>1;
	if(l<=mid)update(rt*2,l,r,hh);
	if(r>mid)update(rt*2+1,l,r,hh);
	if(tree[rt].tag==0)tree[rt].rlen=tree[rt*2].rlen+tree[rt*2+1].rlen;
}

signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld%lld%lld",&x1,&yi,&x2,&y2);
		line[2*i-1].x1=x1,line[2*i-1].x2=x2,line[2*i-1].y=yi,line[2*i-1].c=1;
		line[2*i].x1=x1,line[2*i].x2=x2,line[2*i].y=y2,line[2*i].c=2;
		xx[2*i-1]=x1;xx[2*i]=x2;
	}
	sort(xx+1,xx+2*n+1);
	sort(line+1,line+2*n+1,cmp);
	int cnt=unique(xx+1,xx+2*n+1)-xx-1;
	build(1,1,cnt-1);
	for(int i=1;i<=cnt*2;i++){
		cout<<tree[i].hl<<" "<<tree[i].hr<<endl;
	} 
	for(int i=1;i<2*n;i++){
		int p,q;
		p=lower_bound(xx+1,xx+2*n+1,line[i].x1)-xx;
		q=lower_bound(xx+1,xx+2*n+1,line[i].x2)-xx-1;
		update(1,p,q,line[i].c);
		ans+=tree[1].rlen*(line[i+1].y-line[i].y);
	}
	printf("%lld",ans);
}
2023/9/26 20:22
加载中...