【kd-tree】bzoj4066 简单题-白红宇

【kd-tree】bzoj4066 简单题

阅读量：5837 次

发布时间：2019-06-18

本文共 2692 字，大约阅读时间需要 8 分钟。

同p1176。

#include
     
      #include
      
       #include
       
        using namespace std;#define N 200011#define KD 2//Î¬¶ÈÊýint qp[2][2];int n,root=1,m;bool dn;struct Node{    int minn[KD],maxx[KD],p[KD],w,ch[2],sumv;    void Init()      {        for(int i=0;i
        
         >1);    nth_element(T+l,T+m,T+r+1);    T[m].Init();    if(l!=m) T[m].ch[0]=Buildtree(l,m-1,d^1);    if(m!=r) T[m].ch[1]=Buildtree(m+1,r,d^1);    Update(m);    return m;}void Insert(int rt=root,bool d=0){    bool f=(T[n].p[d]>T[rt].p[d]);    if(T[rt].ch[f]) Insert(T[rt].ch[f],d^1);    else T[rt].ch[f]=n;    Update(rt);}int ans;void Query(int rt=root){    if(T[rt].p[0] >= qp[0][0] && T[rt].p[0] <= qp[1][0]    && T[rt].p[1] >= qp[0][1] && T[rt].p[1] <= qp[1][1])      ans+=T[rt].w;    for(int i=0;i<2;++i)      if(T[rt].ch[i]      && T[T[rt].ch[i]].maxx[0] >= qp[0][0] && T[T[rt].ch[i]].minn[0] <= qp[1][0]      && T[T[rt].ch[i]].maxx[1] >= qp[0][1] && T[T[rt].ch[i]].minn[1] <= qp[1][1])        {          if(T[T[rt].ch[i]].minn[0] >= qp[0][0] && T[T[rt].ch[i]].maxx[0] <= qp[1][0]          && T[T[rt].ch[i]].minn[1] >= qp[0][1] && T[T[rt].ch[i]].maxx[1] <= qp[1][1])            ans+=T[T[rt].ch[i]].sumv;          else            Query(T[rt].ch[i]);        }}int op[N],X1[N],Y1[N],X2[N],Y2[N],Vs[N];int main(){//  freopen("bzoj4066.in","r",stdin);//  freopen("bzoj4066.out","w",stdout);//  for(int i=1;i<=1000000;++i);    scanf("%d",&m); m=0;    while(1)      {        ++m;        scanf("%d",&op[m]);        if(op[m]==3)          {            --m;            break;          }        if(op[m]==1)          {            scanf("%d%d%d",&X1[m],&Y1[m],&Vs[m]);            ++n;          }        else          scanf("%d%d%d%d",&X1[m],&Y1[m],&X2[m],&Y2[m]);      }    int blo=(int)sqrt((double)n*log2((double)n));    n=0;    for(int i=1;i<=m;++i)      {        if(op[i]==1)          {            ++n;            T[n].p[0]=X1[i]; T[n].p[0]^=ans;            T[n].p[1]=Y1[i]; T[n].p[1]^=ans;            T[n].w=Vs[i]; T[n].w^=ans;//          printf("Insert%d:(%d,%d):%d\n",n,T[n].p[0],T[n].p[1],T[n].w);            T[n].Init();            if(n>1)              Insert();            if(blo==1 || blo==0 || n%blo==0)              {                Clear();                Buildtree();                root=(1+n>>1);              }          }        else          {            qp[0][0]=X1[i]; qp[0][0]^=ans;            qp[0][1]=Y1[i]; qp[0][1]^=ans;            qp[1][0]=X2[i]; qp[1][0]^=ans;            qp[1][1]=Y2[i]; qp[1][1]^=ans;            ans=0;            if(n)              Query();            printf("%d\n",ans);          }      }}