P8734求调玄关有注释
查看原帖
P8734求调玄关有注释
677626
xiehy楼主2024/8/16 20:27

全wa 过了样例



#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
const double eps=1e-6;
int read(){
	int flag=1;
	int num=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')flag=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		num=(ch^48)+(num<<1)+(num<<3);
		ch=getchar();
	}
	return flag*num;
}
int n,now,p[N<<1];
struct segment{
	int l,r;
	int mline,d;
}b[N<<1];
struct tree{
	int l,r;
	ll cnt,oddnumber,even;
	ll len;
}tr[N<<3];
bool cmp(segment a,segment b){
	return a.mline<b.mline;
}
void build(int u,int l,int r){
//	cout<<"u="<<u<<"	l="<<l<<"	r="<<r<<endl;
	tr[u].l=l,tr[u].r=r;
	tr[u].len=p[r+1]-p[l];
//	cout<<"now="<<u<<"	sum"<<tr[u].len<<endl;
	if(l==r)return;
	int mid=l+r>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
}
void update(int u,int l,int r,int num){
	if(tr[u].r<l||tr[u].l>r)return;//cout<<"yes"<<endl;
	if(tr[u].l>=l&&tr[u].r<=r){
		tr[u].cnt+=num;
		
	}
	else{
		update(u<<1,l,r,num);//规避递归叶子结点,同时减少不必要的搜索,维护懒标记
		update(u<<1|1,l,r,num);
	}
	if(tr[u].l==tr[u].r){
		if(!tr[u].cnt)tr[u].oddnumber=tr[u].even=0;
		else{
			if(tr[u].cnt&1){//奇数
				tr[u].oddnumber=tr[u].len;
				tr[u].even=0;
			}
			else{
				tr[u].oddnumber=0;
				tr[u].even=tr[u].len;
			}
		}
	}
	else{
		if(!tr[u].cnt){
			tr[u].oddnumber=tr[u<<1].oddnumber+tr[u<<1|1].oddnumber;
			tr[u].even=tr[u<<1].even+tr[u<<1|1].even;
		}
		else{
			if(tr[u].cnt&1){//奇数
				tr[u].oddnumber=tr[u<<1].even+tr[u<<1|1].even;
				tr[u].even=tr[u].len-tr[u].oddnumber;
			}
			else{
				tr[u].oddnumber=tr[u<<1].oddnumber+tr[u<<1|1].oddnumber;
				tr[u].even=tr[u].len-tr[u].oddnumber;
			}
		}
	}
}
ll ans1,ans2,cnt;
int main(){
	cin>>n;
	for(int i=1,mx1,mx2,my1,my2;i<=n;i++){
		scanf("%d%d%d%d",&mx1,&my1,&mx2,&my2);
		b[++now]=segment{mx1,mx2,my1,1};
		p[now]=mx1;
		b[++now]=segment{mx1,mx2,my2,-1};
		p[now]=mx2;
	}
	sort(b+1,b+1+now,cmp);
	sort(p+1,p+1+now),cnt=unique(p+1,p+now+1)-p-1;
	//cout<<cnt<<endl;
	build(1,1,cnt-1);
	for(int i=1;i<=n*2;i++){
		b[i].l=lower_bound(p+1,p+1+cnt,b[i].l)-p;
	//	cout<<"l:"<<b[i].l<<endl;
		b[i].r=lower_bound(p+1,p+1+cnt,b[i].r)-p;
	//	cout<<"r:"<<b[i].r<<endl<<endl;
		update(1,b[i].l,b[i].r-1,b[i].d);
		ans1+=tr[1].oddnumber*(b[i+1].mline-b[i].mline);//奇数
		ans2+=tr[1].even*(b[i+1].mline-b[i].mline);//偶数
	}
	
	cout<<ans1<<endl;
	cout<<ans2<<endl;
	return 0;
}
2024/8/16 20:27
加载中...