[kd-tree] Luogu P4148 简单题

 

 

 题解

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

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> 
using namespace std;
const int N=200010;
struct node{int x[2],w;}P[N];
struct Node{int mn[2],mx[2],sum,ls,rs,sz;node p;}t[N];
int n,ans,root,G,top,cnt,Q[N];
int newnode() { return top?Q[top--]:++cnt; }
int operator < (node a,node b) { return a.x[G]<b.x[G]; }
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; }
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; }
void change(int d,int x) 
{
    if (t[d].ls) change(t[d].ls,x);
    P[t[t[d].ls].sz+x+1]=t[d].p,Q[++top]=d;
    if (t[d].rs) change(t[d].rs,x+t[t[d].ls].sz+1);
}
void pushup(int d)
{
    int l=t[d].ls,r=t[d].rs;
    for (int i=0;i<=1;i++)
    {
        t[d].mn[i]=t[d].mx[i]=t[d].p.x[i];
        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]);
        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]);
    }
    t[d].sum=t[l].sum+t[r].sum+t[d].p.w,t[d].sz=t[l].sz+t[r].sz+1;
}
int build(int d,int l,int r)
{
    if (l>r) return 0;
    int mid=l+r>>1,k=newnode();
    G=d,nth_element(P+l,P+mid,P+r+1),t[k].p=P[mid];
    t[k].ls=build(d^1,l,mid-1),t[k].rs=build(d^1,mid+1,r),pushup(k);
    return k;
}
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); }
void insert(int &d,node l,int r)
{
    if (!d) { d=newnode(),t[d].ls=t[d].rs=0,t[d].p=l,pushup(d); return; }
    if (l.x[r]<=t[d].p.x[r]) insert(t[d].ls,l,r^1); else insert(t[d].rs,l,r^1);
    pushup(d),check(d,r);
}
int query(int d,int l,int r,int L,int R)
{
    if (!d) return 0;
    int w=0;
    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;
    if (pd2(l,r,L,R,t[d].mn[0],t[d].mn[1],t[d].mx[0],t[d].mx[1])) return 0;
    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;
    return w+=query(t[d].ls,l,r,L,R)+query(t[d].rs,l,r,L,R);
}
int main()
{
    scanf("%d",&n);
    for (int op,x,y,z,w;;)        
    {
        scanf("%d",&op);
        if (op==3) break;
        if (op==1) scanf("%d%d%d",&x,&y,&z),insert(root,(node){x^ans,y^ans,z^ans},0);
        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);
    }
}