[kd-tree] Luogu P4148 简单题

时间:2021-11-25 20:32:18

[kd-tree] Luogu P4148 简单题

 

 

 题解

  • 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 }