简单题（K-D Tree）

简单题不简单……
我们把单点加操作改成插入一个权值为增加量的点，将问题转化成询问一个矩阵中所有点的和，用 \(K-D\ Tree\) 维护，时间复杂度 \(O(n\sqrt{n})\)
\(Code\ Below:\)
// luogu-judger-enable-o2

#include <bits/stdc++.h>

using namespace std;

const int maxn=500000+10;

const double alpha=0.75;

int n,D,rt,cnt,tot,rub[maxn],top;

struct node{

    int d[2],val;

}a[maxn];

inline bool operator < (const node &a,const node &b){

    return a.d[D]<b.d[D];

}

struct KD_Tree{

    int d[2],Max[2],Min[2],ch[2],val,siz,sum;

    inline void init(){

        d[0]=d[1]=Max[0]=Max[1]=Min[0]=Min[1]=ch[0]=ch[1]=val=siz=sum=0;

    }

    inline void get(node a){

        Max[0]=Min[0]=d[0]=a.d[0];

        Max[1]=Min[1]=d[1]=a.d[1];

        siz=1;val=sum=a.val;

    }

}t[maxn];

inline int read(){

    register int x=0,f=1;char ch=getchar();

    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}

    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

    return (f==1)?x:-x;

}

inline int newnode(){

    int x=top?rub[top--]:++cnt;

    t[x].init();return x;

}

inline void update(int x,int y){

    t[x].Max[0]=max(t[x].Max[0],t[y].Max[0]);

    t[x].Max[1]=max(t[x].Max[1],t[y].Max[1]);

    t[x].Min[0]=min(t[x].Min[0],t[y].Min[0]);

    t[x].Min[1]=min(t[x].Min[1],t[y].Min[1]);

}

inline void pushup(int x){

    t[x].siz=t[t[x].ch[0]].siz+t[t[x].ch[1]].siz+1;

    t[x].sum=t[t[x].ch[0]].sum+t[t[x].ch[1]].sum+t[x].val;

    if(t[x].ch[0]) update(x,t[x].ch[0]);

    if(t[x].ch[1]) update(x,t[x].ch[1]);

}

int build(int l,int r,int now){

    int mid=(l+r)>>1,x=newnode();D=now;

    nth_element(a+l,a+mid,a+r+1);

    t[x].get(a[mid]);

    if(l<mid) t[x].ch[0]=build(l,mid-1,now^1);

    if(mid<r) t[x].ch[1]=build(mid+1,r,now^1);

    pushup(x);return x;

}

void del(int x){

    if(t[x].ch[0]) del(t[x].ch[0]);

    a[++tot].d[0]=t[x].d[0];

    a[tot].d[1]=t[x].d[1];

    a[tot].val=t[x].val;

    rub[++top]=x;

    if(t[x].ch[1]) del(t[x].ch[1]);

}

void check(int &x,int now){

    if(1.0*max(t[t[x].ch[0]].siz,t[t[x].ch[1]].siz)>1.0*alpha*t[x].siz)

        tot=0,del(x),x=build(1,tot,now);

}

void insert(int &x,node c,int now){

    if(!x){

        x=newnode();

        t[x].get(c);

        return ;

    }

    if(c.d[now]<=t[x].d[now]) insert(t[x].ch[0],c,now^1);

    else insert(t[x].ch[1],c,now^1);

    pushup(x);check(x,now);

}

int query(int x,int x1,int x2,int y1,int y2){

    if(t[x].Max[0]<x1||t[x].Min[0]>x2||t[x].Max[1]<y1||t[x].Min[1]>y2) return 0;

    if(t[x].Max[0]<=x2&&t[x].Min[0]>=x1&&t[x].Max[1]<=y2&&t[x].Min[1]>=y1) return t[x].sum;

    int ans=0;

    if(t[x].d[0]<=x2&&t[x].d[0]>=x1&&t[x].d[1]<=y2&&t[x].d[1]>=y1) ans=t[x].val;

    if(t[x].ch[0]) ans+=query(t[x].ch[0],x1,x2,y1,y2);

    if(t[x].ch[1]) ans+=query(t[x].ch[1],x1,x2,y1,y2);

    return ans;

}

int main()

{

    n=read();

    int op,x,y,z,x1,x2,y1,y2,lastans=0;

    while(1){

        op=read();

        if(op==1){

            x=read()^lastans,y=read()^lastans,z=read()^lastans;

            insert(rt,(node){x,y,z},0);

        }

        if(op==2){

            x1=read()^lastans,y1=read()^lastans,x2=read()^lastans,y2=read()^lastans;

            printf("%d\n",lastans=query(rt,x1,x2,y1,y2));

        }

        if(op==3) break;

    }

    return 0;

}
巴特西

简单题（K-D Tree）

最新文章

热门文章
