K-D Tree 60pts TLE 求调

悬赏关注。

//K-D Tree
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
struct Node
{
    int x,y,w,sumw,lc,rc,minx,miny,maxx,maxy;
};
int n,max_size,rt[30];
vector<Node> kdt[30];
bool xcmp(const Node &x,const Node &y)
{
    return x.x<y.x;
}
bool ycmp(const Node &x,const Node &y)
{
    return x.y<y.y;
}
vector<Node> pre;
int x,y,x5,y5,x6,y6,lc,rc;
int build(int l,int r,int cmd)
{
    int mid=(l+r)>>1;
    if(cmd==0) nth_element(pre.begin()+l,pre.begin()+mid,pre.begin()+r+1,xcmp);
    else nth_element(pre.begin()+l,pre.begin()+mid,pre.begin()+r+1,ycmp);
    pre[mid].sumw=pre[mid].w;
    pre[mid].minx=pre[mid].x;
    pre[mid].maxx=pre[mid].x;
    pre[mid].miny=pre[mid].y;
    pre[mid].maxy=pre[mid].y;
    if(l<mid)
        {
            pre[mid].lc=build(l,mid-1,1-cmd);
            int llc=pre[mid].lc;
            pre[mid].sumw+=pre[llc].sumw;
            pre[mid].minx=min(pre[mid].minx,pre[llc].minx);
            pre[mid].maxx=max(pre[mid].maxx,pre[llc].maxx);
            pre[mid].miny=min(pre[mid].miny,pre[llc].miny);
            pre[mid].maxy=max(pre[mid].maxy,pre[llc].maxy);
        }
    else pre[mid].lc=-1;
    if(mid<r)
        {
            pre[mid].rc=build(mid+1,r,1-mid);
            int rrc=pre[mid].rc;
            pre[mid].sumw+=pre[rrc].sumw;
            pre[mid].minx=min(pre[mid].minx,pre[rrc].minx);
            pre[mid].maxx=max(pre[mid].maxx,pre[rrc].maxx);
            pre[mid].miny=min(pre[mid].miny,pre[rrc].miny);
            pre[mid].maxy=max(pre[mid].maxy,pre[rrc].maxy);
        }
    else pre[mid].rc=-1;
    return mid;
}
void modify(int x,int y,int num)
{
    pre.push_back((Node)
    {
        x,y,num,num,-1,-1,x,y,x,y
    });
    int size_2=0;
    rt[size_2]=0;
    while(!kdt[size_2].empty())
        {
            for(int i=0; i<kdt[size_2].size(); i++)
                {
                    pre.push_back(kdt[size_2][i]);
                }
            kdt[size_2].clear();
            rt[size_2]=-1;
            size_2++;
            rt[size_2]=build(0,(1<<size_2)-1,0);
        }
    max_size=max(max_size,size_2);
    for(int i=0; i<pre.size(); i++)
        {
            kdt[size_2].push_back(pre[i]);
        }
    pre.clear();
}
int sum(int size_2,int id,int x1,int y1,int x2,int y2,int x3,int y3,int x4,int y4)
{
    if(x1>=x3  &&  y1>=y3  &&  x2<=x4  &&  y2<=y4)
        {
            return kdt[size_2][id].sumw;
        }
    if(x1>x4  ||  y1>y4  ||  x2<x3  ||  y2<y3)
        {
            return 0;
        }
    int ans=0;
    x=kdt[size_2][id].x,y=kdt[size_2][id].y;
    if(x>=x3  &&  y>=y3  &&  x<=x4  &&  y<=y4)
        {
            ans+=kdt[size_2][id].w;
        }
    int llc=kdt[size_2][id].lc;
    int rrc=kdt[size_2][id].rc;
    if(llc!=-1)
        {
            x5=kdt[size_2][llc].minx;
            y5=kdt[size_2][llc].miny;
            x6=kdt[size_2][llc].maxx;
            y6=kdt[size_2][llc].maxy;
            ans+=sum(size_2,llc,x5,y5,x6,y6,x3,y3,x4,y4);
        }
    if(rrc!=-1)
        {
            x5=kdt[size_2][rrc].minx;
            y5=kdt[size_2][rrc].miny;
            x6=kdt[size_2][rrc].maxx;
            y6=kdt[size_2][rrc].maxy;
            ans+=sum(size_2,rrc,x5,y5,x6,y6,x3,y3,x4,y4);
        }
    return ans;
}
int query(int x1,int y1,int x2,int y2)
{
    int ans=0;
    for(int i=0; i<=max_size; i++)
        {
            if(!kdt[i].empty())
                {
                    ans+=sum(i,rt[i],kdt[i][rt[i]].minx,kdt[i][rt[i]].miny,kdt[i][rt[i]].maxx,kdt[i][rt[i]].maxy,x1,y1,x2,y2);
                }
        }
    return ans;
}
int main()
{
    memset(rt,-1,sizeof(rt));
    int cmd,lastans=0;
    scanf("%d",&n);
    while(~scanf("%d",&cmd)  &&  cmd!=3)
        {
            if(cmd==1)
                {
                    int x,y,num;
                    scanf("%d %d %d",&x,&y,&num);
                    x^=lastans;
                    y^=lastans;
                    num^=lastans;
                    modify(x,y,num);
                }
            else
                {
                    int x1,y1,x2,y2;
                    scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
                    x1^=lastans;
                    y1^=lastans;
                    x2^=lastans;
                    y2^=lastans;
                    lastans=query(x1,y1,x2,y2);
                    printf("%d\n",lastans);
                }
        }
    return 0;
}