题解
- kd-tree练手题,这题可以将时间T弄上,就是个三维偏序问题,可以直接cdq分治就好了
- 那么考虑kd-tree怎么做,首先对于修改操作,类似于插入一个点
- 对于查询操作,我们可以维护每一棵子树中所有点x和y坐标的最大/最小值
- 如果当前子树整棵树都在当前查询矩形内,就可以直接返回这棵子树中的权值和
- 如果当前子树整棵树都不在当前查询矩形内,就可以直接返回0
- 否则,先查询当前节点代表的点是否在查询矩形中,然后递归查询当前节点的两个子节点
- 还有如果kd-tree不平衡的话,可以类似于替罪羊树直接暴力重建
代码
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 const int N=200010; 7 struct node{int x[2],w;}P[N]; 8 struct Node{int mn[2],mx[2],sum,ls,rs,sz;node p;}t[N]; 9 int n,ans,root,G,top,cnt,Q[N]; 10 int newnode() { return top?Q[top--]:++cnt; } 11 int operator < (node a,node b) { return a.x[G]<b.x[G]; } 12 bool pd1(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; } 13 bool pd2(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; } 14 void change(int d,int x) 15 { 16 if (t[d].ls) change(t[d].ls,x); 17 P[t[t[d].ls].sz+x+1]=t[d].p,Q[++top]=d; 18 if (t[d].rs) change(t[d].rs,x+t[t[d].ls].sz+1); 19 } 20 void pushup(int d) 21 { 22 int l=t[d].ls,r=t[d].rs; 23 for (int i=0;i<=1;i++) 24 { 25 t[d].mn[i]=t[d].mx[i]=t[d].p.x[i]; 26 if (l) t[d].mn[i]=min(t[d].mn[i],t[l].mn[i]),t[d].mx[i]=max(t[d].mx[i],t[l].mx[i]); 27 if (r) t[d].mn[i]=min(t[d].mn[i],t[r].mn[i]),t[d].mx[i]=max(t[d].mx[i],t[r].mx[i]); 28 } 29 t[d].sum=t[l].sum+t[r].sum+t[d].p.w,t[d].sz=t[l].sz+t[r].sz+1; 30 } 31 int build(int d,int l,int r) 32 { 33 if (l>r) return 0; 34 int mid=l+r>>1,k=newnode(); 35 G=d,nth_element(P+l,P+mid,P+r+1),t[k].p=P[mid]; 36 t[k].ls=build(d^1,l,mid-1),t[k].rs=build(d^1,mid+1,r),pushup(k); 37 return k; 38 } 39 void check(int &d,int x) { if (t[d].sz*0.75<t[t[d].ls].sz||t[d].sz*0.75<t[t[d].rs].sz) change(d,0),d=build(x,1,t[d].sz); } 40 void insert(int &d,node l,int r) 41 { 42 if (!d) { d=newnode(),t[d].ls=t[d].rs=0,t[d].p=l,pushup(d); return; } 43 if (l.x[r]<=t[d].p.x[r]) insert(t[d].ls,l,r^1); else insert(t[d].rs,l,r^1); 44 pushup(d),check(d,r); 45 } 46 int query(int d,int l,int r,int L,int R) 47 { 48 if (!d) return 0; 49 int w=0; 50 if (pd1(l,r,L,R,t[d].mn[0],t[d].mn[1],t[d].mx[0],t[d].mx[1])) return t[d].sum; 51 if (pd2(l,r,L,R,t[d].mn[0],t[d].mn[1],t[d].mx[0],t[d].mx[1])) return 0; 52 if (pd1(l,r,L,R,t[d].p.x[0],t[d].p.x[1],t[d].p.x[0],t[d].p.x[1])) w+=t[d].p.w; 53 return w+=query(t[d].ls,l,r,L,R)+query(t[d].rs,l,r,L,R); 54 } 55 int main() 56 { 57 scanf("%d",&n); 58 for (int op,x,y,z,w;;) 59 { 60 scanf("%d",&op); 61 if (op==3) break; 62 if (op==1) scanf("%d%d%d",&x,&y,&z),insert(root,(node){x^ans,y^ans,z^ans},0); 63 else scanf("%d%d%d%d",&x,&y,&z,&w),x^=ans,y^=ans,z^=ans,w^=ans,ans=query(root,x,y,z,w),printf("%d\n",ans); 64 } 65 }