[文章目录]
Description
你有一个N*N的棋盘，每个格子内有一个整数，初始时的时候全部为0，现在需要维护两种操作：
1 x y A : 1<=x,y<=N，A是正整数,将格子x,y里的数字加上A
2 x1 y1 x2 y2: 1<=x1<= x2<=N 1<=y1<= y2<=N,输出x1 y1 x2 y2这个矩形内的数字和
KD-tree模板题。
对于二维平面上一个矩形区域，在KD-tree上只会有O(√n)个关键点与之对应。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
inline char nc()
{
static char buf[100000],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x)
{
x=0; char f=0,ch=nc();
while(!isdigit(ch)) {if(ch=='-') f=1; ch=nc();}
while(isdigit(ch)) x=x*10+(ch^'0'),ch=nc();
if(f) x=-x;
}
int n,d,rot,ans,cgg;
double arf=0.8;
struct KD_tree
{
int p[2],mi[2],mx[2],ls,rs,w,sum,siz;
void clear()
{
mi[0]=mx[0]=p[0];
mi[1]=mx[1]=p[1];
sum=w; siz=1;
ls=rs=0;
}
}t[201000];
bool operator < (KD_tree x,KD_tree y)
{
return x.p[d]==y.p[d] ? x.p[d^1] < y.p[d^1] : x.p[d] < y.p[d];
}
void pushup(int p,int s)
{
t[p].mi[0]=min(t[p].mi[0],t[s].mi[0]);
t[p].mx[0]=max(t[p].mx[0],t[s].mx[0]);
t[p].mi[1]=min(t[p].mi[1],t[s].mi[1]);
t[p].mx[1]=max(t[p].mx[1],t[s].mx[1]);
t[p].siz+=t[s].siz;
t[p].sum+=t[s].sum;
}
int cg[201000];
bool cmp(int x,int y){return t[x]<t[y];}
void flatten(int x)
{
if(!x) return ;
flatten(t[x].ls);
flatten(t[x].rs);
cg[++cgg]=x; t[x].clear();
}
int build(int l,int r,int fl)
{
int mid=(l+r)>>1; d=fl;
nth_element(cg+l,cg+mid,cg+r+1,cmp);
int re=cg[mid];
if(l<mid) pushup(re,t[re].ls=build(l,mid-1,fl^1));
if(r>mid) pushup(re,t[re].rs=build(mid+1,r,fl^1));
return re;
}
void rebuild(int &x,int D)
{
cgg=0; flatten(x);
x=build(1,cgg,D);
}
void insert(int &p,int k,int fl,int D)
{
if(!p) {p=k; return ;}
pushup(p,k); d=D;
if(t[k]<t[p])
{
if(!fl&&t[t[p].ls].siz+1>t[p].siz*arf) insert(t[p].ls,k,1,D^1),rebuild(p,D);
else insert(t[p].ls,k,fl,D^1);
}
else
{
if(!fl&&t[t[p].rs].siz+1>t[p].siz*arf) insert(t[p].rs,k,1,D^1),rebuild(p,D);
else insert(t[p].rs,k,fl,D^1);
}
}
void query(int p,int x,int y,int dx,int dy)
{
if(!p||dx<t[p].mi[0]||x>t[p].mx[0]||dy<t[p].mi[1]||y>t[p].mx[1]) return ;
if(x<=t[p].mi[0]&&dx>=t[p].mx[0]&&y<=t[p].mi[1]&&dy>=t[p].mx[1])
{
ans+=t[p].sum;
return ;
}
if(t[p].p[0]>=x&&t[p].p[0]<=dx&&t[p].p[1]>=y&&t[p].p[1]<=dy) ans+=t[p].w;
query(t[p].ls,x,y,dx,dy);
query(t[p].rs,x,y,dx,dy);
}
int main()
{
int sw,x,y,dx,dy; read(sw);
while(1)
{
read(sw);
if(sw==3) break;
if(sw==1)
{
++n;
read(t[n].p[0]); read(t[n].p[1]); read(t[n].w);
t[n].p[0]^=ans; t[n].p[1]^=ans; t[n].w^=ans;
t[n].clear(); insert(rot,n,0,0);
}
else
{
read(x); read(y); x^=ans; y^=ans;
read(dx); read(dy); dx^=ans; dy^=ans;
ans=0; query(rot,x,y,dx,dy);
printf("%d\n",ans);
}
}
return 0;
}