【kd-tree】bzoj1176 [Balkan2007]Mokia-白红宇

【kd-tree】bzoj1176 [Balkan2007]Mokia

阅读量：6812 次

发布时间：2019-06-26

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

裸题不多说，注意在sqrt(n*log(n))次插入后重构树以保持深度。

#include
     
      #include
      
       #include
       
        using namespace std;#define N 170011#define KD 2//Î¬¶ÈÊýint qp[2][2];int n,root=1,m;int Begin;bool dn;struct Node{    int minn[KD],maxx[KD],p[KD],ch[2];    int sumv,w;    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;}inline 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];int Vs[N];int main(){//  freopen("data7.in","r",stdin);//  freopen("bzoj4066.out","w",stdout);    scanf("%d%d",&Begin,&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[1]=Y1[i];            T[n].w=Vs[i];            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][1]=Y1[i];            qp[1][0]=X2[i];            qp[1][1]=Y2[i];            ans=0;            if(n)              Query();            printf("%d\n",ans+(qp[1][1]-qp[1][0]+1)*(qp[0][1]-qp[0][0]+1)*Begin);          }      }    return 0;}