求助
  • 板块P4148 简单题
  • 楼主_tan_
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/12/19 19:36
  • 上次更新2024/12/19 20:05:47
查看原帖
求助
693327
_tan_楼主2024/12/19 19:36

怎么WA了,感觉和第一篇题解一样啊

#include<bits/stdc++.h>
#define ll long long
#define reg register
#define db double
#define il inline
using namespace std;
void read(int &x){x=0;int f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}x*=f;}
void read(ll &x){x=0;int f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}x*=f;}
const int N=2e5+5;
int n;
struct point{int x[2],w;}p[N];
struct node{int mi[2],mx[2],sum,ls,rs,sz;point tp;}tree[N];
int ans;
int rub[N],rubtot,tot;
int WD;
int operator <(point a,point b){
	return a.x[WD]<b.x[WD];
}
int newnode(){
	if(rubtot)return rub[rubtot--];
	else return ++tot;
}
void push_up(int k){
	int l=tree[k].ls,r=tree[k].rs;
	//cout<<l<<' '<<r<<endl;
	for(int i=0;i<=1;i++){
		tree[k].mi[i]=tree[k].mx[i]=tree[k].tp.x[i];
		if(l)tree[k].mi[i]=min(tree[k].mi[i],tree[l].mi[i]);
		if(r)tree[k].mi[i]=min(tree[k].mi[i],tree[r].mi[i]);
		if(l)tree[k].mx[i]=max(tree[k].mx[i],tree[l].mx[i]);
		if(r)tree[k].mx[i]=max(tree[k].mx[i],tree[r].mx[i]);
	}
	tree[k].sum=tree[l].sum+tree[r].sum+tree[k].tp.w;
	tree[k].sz=tree[l].sz+tree[r].sz+1;
}
int build(int l,int r,int wd){
	if(l<r)return 0;
	int mid=(l+r)/2,k=newnode();
	WD=wd;nth_element(p+l,p+mid,p+r+1),tree[k].tp=p[mid];
	tree[k].ls=build(l,mid-1,wd^1);tree[k].rs=build(mid+1,r,wd^1);
	push_up(k);return k;
}
int in(int x1,int y1,int x2,int y2,int X1,int Y1,int X2,int Y2){
	return (X1>=x1&&X2<=x2&&Y1>=y1&&Y2<=y2);
}
int out(int x1,int y1,int x2,int y2,int X1,int Y1,int X2,int Y2){
	return (x1>X2||x2<X1||y1>Y2||y2<Y1);
}
void pia(int k,int num){
	if(tree[k].ls)pia(tree[k].ls,num);
	p[tree[tree[k].ls].sz+num+1]=tree[k].tp,rub[++rubtot]=k;
	if(tree[k].rs)pia(tree[k].rs,num+tree[tree[k].ls].sz+1);
}
void check(int &k,int wd){
	if(tree[k].sz*0.75<tree[tree[k].ls].sz||tree[k].sz*0.75<tree[tree[k].rs].sz){
		pia(k,0);k=build(1,tree[k].sz,wd);
	}
}
int query(int k,int x1,int y1,int x2,int y2){
	if(!k)return 0;
	int re=0;
	if(in(x1,y1,x2,y2,tree[k].mi[0],tree[k].mi[1],tree[k].mx[0],tree[k].mx[1]))return tree[k].sum;
	if(out(x1,y1,x2,y2,tree[k].mi[0],tree[k].mi[1],tree[k].mx[0],tree[k].mx[1]))return 0;
	if(in(x1,y1,x2,y2,tree[k].tp.x[0],tree[k].tp.x[1],tree[k].tp.x[0],tree[k].tp.x[1]))re=tree[k].tp.w;
	//cout<<"this";
	return re+query(tree[k].ls,x1,y1,x2,y2)+query(tree[k].rs,x1,y1,x2,y2);
}
int rt;
void ins(int &k,point tmp,int wd){
	if(!k){
		k=newnode();tree[k].ls=tree[k].rs=0;tree[k].tp=tmp;push_up(k);return;
	}
	if(tmp.x[wd]<=tree[k].tp.x[wd])ins(tree[k].ls,tmp,wd^1);
	else ins(tree[k].rs,tmp,wd^1);
	push_up(k);check(k,wd);
}
int main(){
	read(n);
	while(1){
		int op,x,y,xx,yy;
		read(op);
		if(op==3)return 0;
		if(op==1){
			read(x);read(y);read(xx);x^=ans;y^=ans;xx^=ans;
			ins(rt,(point){x,y,xx},0);
		}else{
			read(x);read(y);read(xx);read(yy);x^=ans;y^=ans;xx^=ans;yy^=ans;
			ans=query(rt,x,y,xx,yy);printf("%d\n",ans);
		}
	}
	
	return 0;
}

2024/12/19 19:36
加载中...