20pts求助
查看原帖
20pts求助
285617
黑影洞人楼主2023/6/9 17:31
#include<cstdio>
#include<algorithm>
#define N 214514
using namespace std;
int n;
struct node{int x[2],val;}b[N];
int deg;
int rt;
bool cmp(node a,node b){return a.x[deg]<b.x[deg];}
struct kdt{
	double alpha=0.75;
	int lson[N],rson[N];
	node a[N];
	int lx[N],rx[N],ly[N],ry[N],val[N],siz[N];
	int st[N],top,tot;
	#define lc lson[p]
	#define rc rson[p]
	int newnode(){if(top)return st[top--];else return ++tot;}
	void del(int p){st[++top]=p;}
	int pushup(int p){
		lx[p]=rx[p]=a[p].x[0];
		ry[p]=ry[p]=a[p].x[1];
		if(lc){
			lx[p]=min(lx[lc],lx[p]),rx[p]=max(rx[lc],rx[p]);
			ly[p]=min(ly[lc],ly[p]),ry[p]=max(ry[lc],ry[p]);
		}
		if(rc){
			lx[p]=min(lx[rc],lx[p]),rx[p]=max(rx[rc],rx[p]);
			ly[p]=min(ly[rc],ly[p]),ry[p]=max(ry[rc],ry[p]);
		}
		val[p]=val[lc]+val[rc]+a[p].val;
		siz[p]=siz[lc]+siz[rc]+1;
		return p;
	}
	int build(int l,int r,int d){
		if(r<l)return 0;int mid=(l+r)/2,p=newnode();
		deg=d;nth_element(b+l,b+mid,b+r+1,cmp);
		a[p]=b[mid];
		lc=build(l,mid-1,d^1);rc=build(mid+1,r,d^1);
		return pushup(p);
	}
	void dfs(int p,int pos){
		if(lc)dfs(lc,pos);
		b[siz[lc]+pos+1]=a[p];del(p);
		if(rc)dfs(rc,siz[lc]+pos+1);
	}
	void rebuild(int &p,int d){
		if(1.0*siz[p]*alpha>=1.0*siz[lc]&&1.0*siz[p]*alpha>=1.0*siz[rc])return;
		dfs(p,0);p=build(1,siz[p],d);
	}
	void insert(int &p,node x,int d){
		if(!p){p=newnode(),lc=rc=0,a[p]=x;pushup(p);return;}
		if(x.x[d]<=a[p].x[d])insert(lc,x,d^1);
		else insert(rc,x,d^1);
		pushup(p);rebuild(p,d);
	}
	int query(int p,int x,int y,int xx,int yy){
		if(!p)return 0;
		int res=0;
		if(lx[p]>=x&&rx[p]<=xx&&ly[p]>=y&&ry[p]<=yy)return val[p];
		if(x>rx[p]||xx<lx[p]||y>ry[p]||yy<ry[p])return 0;
		if(a[p].x[0]>=x&&a[p].x[0]<=xx&&a[p].x[1]>=y&&a[p].x[1]<=yy)res+=a[p].val;
		res+=query(lc,x,y,xx,yy)+query(rc,x,y,xx,yy);
		return res;
	}
}t;
signed main(){
	scanf("%d",&n);
	int la=0;
	while(1){
		int op,x,y,xx,yy,v;
		scanf("%d",&op);
		if(op==1){
			scanf("%d%d%d",&x,&y,&v);
			x^=la,y^=la,v^=la;
			t.insert(rt,(node){x,y,v},0);
		}else if(op==2){
			scanf("%d%d%d%d",&x,&y,&xx,&yy);
			x^=la,y^=la,xx^=la,yy^=la;
			printf("%d\n",la=t.query(rt,x,y,xx,yy));
		}else break;
	}
	return 0;
}



2023/6/9 17:31
加载中...