刚学OI萌新求调KD树
查看原帖
刚学OI萌新求调KD树
626463
Calvin_Wang楼主2024/1/24 21:25

RT

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define lc tr[u].ls
#define rc tr[u].rs
using namespace std;

const int N=5e5+10;
const double alpha=0.7;
struct point{
	int dim[2],val;
	point(){};
	point(int x,int y,int vall){
		dim[0]=x;
		dim[1]=y;
		val=vall;
	}
}order[N];
int cnt,tot,root,top,trst[N],now;
struct kd_tree{
	int ls,rs,mi[2],ma[2],sum,size;
	point p;
}tr[N];

bool cmp(point a,point b){
	return a.dim[now]<b.dim[now];
}

void update(int u){
	for(int i=0;i<2;++i){
		tr[u].mi[i]=tr[u].ma[i]=tr[u].p.dim[i];
		if(lc){
			tr[u].mi[i]=min(tr[u].mi[i],tr[lc].mi[i]);
			tr[u].ma[i]=max(tr[u].ma[i],tr[lc].ma[i]);
		}
		if(rc){
			tr[u].mi[i]=min(tr[u].mi[i],tr[rc].mi[i]);
			tr[u].ma[i]=max(tr[u].ma[i],tr[rc].ma[i]);
		}
	}
	tr[u].sum=tr[lc].sum+tr[rc].sum+tr[u].p.val;
	tr[u].size=tr[lc].size+tr[rc].size+1;
}

void slap(int u){
	if(!u){
		return;
	}
	slap(lc);
	order[++cnt]=tr[u].p;
	trst[++top]=u;
	slap(rc);
}

int build(int l,int r,int d){
	if(l>r){
		return 0;
	}
	int u;
	if(top){
		u=trst[top--];
	}else{
		u=++tot;
	}
	int mid=l+r>>1;
	now=d;
	nth_element(order+1,order+mid,order+r+1,cmp);
	tr[u].p=order[mid];
	lc=build(l,mid-1,d^1);
	rc=build(mid+1,r,d^1);
	update(u);
	return u;
}

bool notbalance(int u){
	if(tr[lc].size>alpha*tr[u].size||tr[rc].size>alpha*tr[u].size){
		return true;
	}
	return false;
}

void insert(int &u,point now,int d){
	if(!u){
		if(top){
			u=trst[top--];
		}else{
			u=++tot;
		}
		lc=rc=0;
		tr[u].p=now;
		update(u);
		return;
	}
	if(now.dim[d]<=tr[u].p.dim[d]){
		insert(lc,now,d^1);
	}else{
		insert(rc,now,d^1);
	}
	update(u);
	if(notbalance(u)){
		cnt=0;
		slap(u);
		u=build(1,tr[u].size,d);
	}
}

int query(int u,int x1,int y1,int x2,int y2){
	if(!u){
		return 0;
	}
	int X1=tr[u].mi[0],Y1=tr[u].mi[1],X2=tr[u].ma[0],Y2=tr[u].ma[1];
	if(x1<=X1&&x2>=X2&&y1<=Y1&&y2>=Y2){
		return tr[u].sum;
	}
	if(x1>X2||x2<X1||y1>Y2||y2<Y1){
		return 0;
	}
	int ans=0;
	X1=X2=tr[u].p.dim[0],Y1=Y2=tr[u].p.dim[1];
	if(x1<=X1&&x2>=X2&&y1<=Y1&&y2>=Y2){
		ans+=tr[u].p.val;
	}
	ans+=query(lc,x1,y1,x2,y2)+query(rc,x1,y1,x2,y2);
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	int ans=0;
	while(1){
		int opt;
		cin>>opt;
		if(opt==1){
			int x,y,val;
			cin>>x>>y>>val;
			x^=ans;
			y^=ans;
			val^=ans;
			insert(root,point(x,y,val),0);
		}else if(opt==2){
			int x1,y1,x2,y2;
			cin>>x1>>y1>>x2>>y2;
			x1^=ans;
			y1^=ans;
			x2^=ans;
			y2^=ans;
			ans=query(root,x1,y1,x2,y2);
			cout<<ans<<endl;
		}else{
			break;
		}
	}
	return 0;
}
2024/1/24 21:25
加载中...