【kd-tree】bzoj1176 [Balkan2007]Mokia

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

#include<cstdio>
#include<cmath>
#include<algorithm>
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<KD;++i)
          minn[i]=maxx[i]=p[i];
        sumv=w;
      }
}T[N];
inline void Clear()
{
    for(int i=1;i<=n;++i)
      T[i].ch[0]=T[i].ch[1]=0;
}
inline void Update(int rt)
{
    T[rt].sumv=T[rt].w;
    for(int i=0;i<2;++i)
      if(T[rt].ch[i])
        {
          T[rt].sumv+=T[T[rt].ch[i]].sumv;
          for(int j=0;j<KD;++j)
            {
              T[rt].minn[j]=min(T[rt].minn[j],T[T[rt].ch[i]].minn[j]);
              T[rt].maxx[j]=max(T[rt].maxx[j],T[T[rt].ch[i]].maxx[j]);
            }
        }
}
bool operator < (const Node &a,const Node &b){return a.p[dn]<b.p[dn];}
inline int Buildtree(int l=1,int r=n,bool d=0)
{
    dn=d;
    int m=(l+r>>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
",ans+(qp[1][1]-qp[1][0]+1)*(qp[0][1]-qp[0][0]+1)*Begin);
          }
      }
    return 0;
}