题解

• kd-tree练手题，这题可以将时间T弄上，就是个三维偏序问题，可以直接cdq分治就好了
• 那么考虑kd-tree怎么做，首先对于修改操作，类似于插入一个点
• 对于查询操作,我们可以维护每一棵子树中所有点x和y坐标的最大/最小值
• 如果当前子树整棵树都在当前查询矩形内，就可以直接返回这棵子树中的权值和
• 如果当前子树整棵树都不在当前查询矩形内，就可以直接返回0
• 否则，先查询当前节点代表的点是否在查询矩形中，然后递归查询当前节点的两个子节点
• 还有如果kd-tree不平衡的话，可以类似于替罪羊树直接暴力重建

代码

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
           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]
         
          =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
          
           Y2||y2
           
            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