用于动态插入以及求某点的最近点的距离(BZOJ2648,BZOJ2716)
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std; int cnt,ans,n,m; struct data{
int x,y;
}point[]; struct kd_node{
int x,y,lc,rc,minx,miny,maxx,maxy;
}tr[]; int dis(int x1,int y1,int x2,int y2){
return(fabs(x1-x2)+fabs(y1-y2));
} int mycomp1(const data&a,const data&b){
return(a.y<b.y);
} int mycomp2(const data&a,const data&b){
return(a.x<b.x);
} void kd_update(int po){
if (tr[po].lc){
tr[po].minx=min(tr[po].minx,tr[tr[po].lc].minx);
tr[po].miny=min(tr[po].miny,tr[tr[po].lc].miny);
tr[po].maxx=max(tr[po].maxx,tr[tr[po].lc].maxx);
tr[po].maxy=max(tr[po].maxy,tr[tr[po].lc].maxy);
};
if (tr[po].rc){
tr[po].minx=min(tr[po].minx,tr[tr[po].rc].minx);
tr[po].miny=min(tr[po].miny,tr[tr[po].rc].miny);
tr[po].maxx=max(tr[po].maxx,tr[tr[po].rc].maxx);
tr[po].maxy=max(tr[po].maxy,tr[tr[po].rc].maxy);
}
}//维护包含子树中所有点的最小的矩形,左下角(minx,miny),右上角(maxx,maxy) void kd_build(int l,int r,int wd){
if (wd) sort(point+l,point+r+,mycomp1);else sort(point+l,point+r+,mycomp2);//实际应选取方差最大的一维
cnt++;
int mid=(l+r)>>,t=cnt;//mid实际应为与平均值最接近的
tr[cnt].x=point[mid].x;tr[cnt].y=point[mid].y;
tr[cnt].minx=point[mid].x;tr[cnt].maxx=point[mid].x;
tr[cnt].miny=point[mid].y;tr[cnt].maxy=point[mid].y;
if (l<mid){
tr[t].lc=cnt+;kd_build(l,mid-,!wd);
};
if (mid<r){
tr[t].rc=cnt+;kd_build(mid+,r,!wd);
}
kd_update(t);
}//构建n点的KD树,每次以一维为标准划分点 void kd_ins(int po,int x,int y,int d){
int son=;
if (d==) son=(x<=tr[po].x);else son=(y<=tr[po].y);
if (son==){
if (tr[po].lc==){
tr[po].lc=++cnt;
tr[cnt].x=x;tr[cnt].y=y;
tr[cnt].minx=x;tr[cnt].maxx=x;
tr[cnt].miny=y;tr[cnt].maxy=y;
}else kd_ins(tr[po].lc,x,y,!d);
}else{
if (tr[po].rc==){
tr[po].rc=++cnt;
tr[cnt].x=x;tr[cnt].y=y;
tr[cnt].minx=x;tr[cnt].maxx=x;
tr[cnt].miny=y;tr[cnt].maxy=y;
}else kd_ins(tr[po].rc,x,y,!d);
}
kd_update(po);
} int dist(int x,int y,int po){
int ret=;
ret+=max(,tr[po].minx-x);
ret+=max(,x-tr[po].maxx);
ret+=max(,tr[po].miny-y);
ret+=max(,y-tr[po].maxy);
return(ret);
}//(x,y)到po子树维护的矩形的最近距离。假设该矩形中铺满点,所以返回值小于等于实际值 void kd_query(int po,int x,int y){
ans=min(ans,dis(x,y,tr[po].x,tr[po].y));
int dl=(tr[po].lc== ? 1e9:dist(x,y,tr[po].lc));
int dr=(tr[po].rc== ? 1e9:dist(x,y,tr[po].rc));
if (dl<dr){
if (dl<ans) kd_query(tr[po].lc,x,y);
if (dr<ans) kd_query(tr[po].rc,x,y);
}else{
if (dr<ans) kd_query(tr[po].rc,x,y);
if (dl<ans) kd_query(tr[po].lc,x,y);
}
}//以dist为估价函数搜寻 int main(){
scanf("%d%d",&n,&m);
for (int i=;i<=n;i++) scanf("%d%d",&point[i].x,&point[i].y);
kd_build(,n,); for (int i=;i<=m;i++){
int opt,x,y;
scanf("%d%d%d",&opt,&x,&y); if (opt==){
kd_ins(,x,y,);
}else{
ans=1e9;
kd_query(,x,y);
printf("%d\n",ans);
}
}
}
____________________________________________
BZOJ4066
单点修改，矩形求和
#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std; int cnt,tcnt,n; struct data{
int x,y,v;
}a[]; struct treenode{
int lc,rc,x,y,minx,miny,maxx,maxy,num,v;
}tr[]; void update(int po){
tr[po].num=tr[tr[po].lc].num+tr[tr[po].rc].num+tr[po].v;
tr[po].minx=min(min(tr[tr[po].lc].minx,tr[tr[po].rc].minx),tr[po].x);
tr[po].miny=min(min(tr[tr[po].lc].miny,tr[tr[po].rc].miny),tr[po].y);
tr[po].maxx=max(max(tr[tr[po].lc].maxx,tr[tr[po].rc].maxx),tr[po].x);
tr[po].maxy=max(max(tr[tr[po].lc].maxy,tr[tr[po].rc].maxy),tr[po].y);
} void insert(int po,int x,int y,int num,int wd){
if (tr[po].x==x&&tr[po].y==y){
tr[po].num+=num;tr[po].v+=num;return;
} int sel;
if (!wd) sel=(tr[po].x<x);else sel=(tr[po].y<y);
if (!sel){
if (!tr[po].lc){
cnt++;
tr[cnt].x=tr[cnt].minx=tr[cnt].maxx=x;
tr[cnt].y=tr[cnt].miny=tr[cnt].maxy=y;
tr[cnt].v=tr[cnt].num=num;
tr[po].lc=cnt;
update(po);
}else insert(tr[po].lc,x,y,num,!wd);
}else{
if (!tr[po].rc){
cnt++;
tr[cnt].x=tr[cnt].minx=tr[cnt].maxx=x;
tr[cnt].y=tr[cnt].miny=tr[cnt].maxy=y;
tr[cnt].v=tr[cnt].num=num;
tr[po].rc=cnt;
update(po);
}else insert(tr[po].rc,x,y,num,!wd);
}
update(po);
} int mycomp1(const data&a,const data&b){
return(a.x<b.x);
} int mycomp2(const data&a,const data&b){
return(a.y<b.y);
} void build(int l,int r,int wd){
if (wd==) sort(a+l,a+r+,mycomp1);else sort(a+l,a+r+,mycomp2);
int mid=(l+r)>>;
int tmp=++tcnt;
tr[tcnt].lc=tr[tcnt].rc=;
tr[tcnt].x=a[mid].x;tr[tcnt].y=a[mid].y;tr[tcnt].v=a[mid].v;
if (l<mid){
tr[tmp].lc=tcnt+;build(l,mid-,!wd);
};
if (r>mid){
tr[tmp].rc=tcnt+;build(mid+,r,!wd);
}
update(tmp);
} int in(int x1,int y1,int x2,int y2,int X1,int Y1,int X2,int Y2){
return(X1<=x1&&Y1<=y1&&X2>=x2&&Y2>=y2);
} int out(int x1,int y1,int x2,int y2,int X1,int Y1,int X2,int Y2){
return(x2<X1||x1>X2||y1>Y2||y2<Y1);
} int query(int po,int x1,int y1,int x2,int y2){
int ret=;
if (in(tr[po].minx,tr[po].miny,tr[po].maxx,tr[po].maxy,x1,y1,x2,y2)) return(tr[po].num); if (in(tr[po].x,tr[po].y,tr[po].x,tr[po].y,x1,y1,x2,y2)) ret+=tr[po].v;
if (!out(tr[tr[po].lc].minx,tr[tr[po].lc].miny,tr[tr[po].lc].maxx,tr[tr[po].lc].maxy,x1,y1,x2,y2)) ret+=query(tr[po].lc,x1,y1,x2,y2);
if (!out(tr[tr[po].rc].minx,tr[tr[po].rc].miny,tr[tr[po].rc].maxx,tr[tr[po].rc].maxy,x1,y1,x2,y2)) ret+=query(tr[po].rc,x1,y1,x2,y2);
return(ret);
} int main(){
scanf("%d",&n);
tr[].miny=tr[].minx=1e9;
tr[].maxx=tr[].maxy=-1e9;
int opt,lastans=,lastrebuild=,root=;
while (scanf("%d",&opt),opt!=){
int x,y,x1,y1,x2,y2,num; if (opt==){
scanf("%d%d%d",&x,&y,&num);
x^=lastans;y^=lastans;num^=lastans;
if (!root){
root=;
cnt++;
tr[cnt].x=tr[cnt].minx=tr[cnt].maxx=x;
tr[cnt].y=tr[cnt].miny=tr[cnt].maxy=y;
tr[cnt].v=tr[cnt].num=num;
}else{
insert(root,x,y,num,);
} if (cnt/>lastrebuild){
for (int i=;i<=cnt;i++) a[i].x=tr[i].x,a[i].y=tr[i].y,a[i].v=tr[i].v;
tcnt=;
build(,cnt,);
lastrebuild++;
}
} if (opt==){
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
x1^=lastans;x2^=lastans;y1^=lastans;y2^=lastans;
lastans=query(,x1,y1,x2,y2);
printf("%d\n",lastans);
}
}
}