贴模板、
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define N 501000 #define inf 0x3f3f3f3f #define d(x,y) (((x)>(y))?((x)-(y)):((y)-(x))) using namespace std; int n,m; int judge; struct Point { int x,y; Point(int _x=0,int _y=0):x(_x),y(_y){} bool operator < (const Point &a)const {return judge?y<a.y:x<a.x;} }P[N<<1]; inline int dis(Point &a,Point &b){return d(a.x,b.x)+d(a.y,b.y);} struct KDT { int son[N<<1][2],cnt,root; int x[N<<1][2],y[N<<1][2]; void init(int a,Point &p) { x[a][0]=x[a][1]=p.x; y[a][0]=y[a][1]=p.y; } void UP(int f,Point &p) { x[f][0]=min(x[f][0],p.x); x[f][1]=max(x[f][1],p.x); y[f][0]=min(y[f][0],p.y); y[f][1]=max(y[f][1],p.y); } void update(int f) { int s; if(son[f][0]) { s=son[f][0]; x[f][0]=min(x[f][0],x[s][0]); y[f][0]=min(y[f][0],y[s][0]); x[f][1]=max(x[f][1],x[s][1]); y[f][1]=max(y[f][1],y[s][1]); } if(son[f][1]) { s=son[f][1]; x[f][0]=min(x[f][0],x[s][0]); y[f][0]=min(y[f][0],y[s][0]); x[f][1]=max(x[f][1],x[s][1]); y[f][1]=max(y[f][1],y[s][1]); } } int maxdis(int a,Point &p) { int ret=0; ret+=max(d(x[a][0],p.x),d(x[a][1],p.x)); ret+=max(d(y[a][0],p.y),d(y[a][1],p.y)); return ret; } int mindis(int a,Point &p) { int ret=0; if(p.x<x[a][0])ret+=x[a][0]-p.x; else if(x[a][1]<p.x)ret+=p.x-x[a][1]; if(p.y<y[a][0])ret+=y[a][0]-p.y; else if(y[a][1]<p.y)ret+=p.y-y[a][1]; return ret; } int newnode(Point &p) { init(++cnt,p); return cnt; } int build(int l,int r,int jd=0) { int mid=l+r>>1,t=0; judge=jd; nth_element(P+l,P+mid,P+r+1); if(l<mid)t=build(l,mid-1,!jd); int q=newnode(P[mid]);son[q][0]=t; if(mid<r)son[q][1]=build(mid+1,r,!jd); update(q); return q; } int Maxdis,Mindis; void querymin(int f,Point &p) { int Dis[3]; Dis[2]=dis(P[f],p); Mindis=min(Mindis,Dis[2]); Dis[0]=Dis[1]=inf; if(son[f][0])Dis[0]=mindis(son[f][0],p); if(son[f][1])Dis[1]=mindis(son[f][1],p); int t=Dis[0]>Dis[1]; if(son[f][t]&&Dis[t]<Mindis)querymin(son[f][t],p); t^=1;if(son[f][t]&&Dis[t]<Mindis)querymin(son[f][t],p); } void querymax(int f,Point &p) { int Dis[3]; Dis[2]=dis(P[f],p); Maxdis=max(Maxdis,Dis[2]); Dis[0]=Dis[1]=0; if(son[f][0])Dis[0]=maxdis(son[f][0],p); if(son[f][1])Dis[1]=maxdis(son[f][1],p); for(int i=2,t=Dis[0]<Dis[1];i--;t^=1) if(son[f][t]&&Dis[t]>Maxdis)querymax(son[f][t],p); } void insert(Point &p,int jd) // 非递归版 { int v=newnode(p); if(!root){root=v;return ;} for(int t,f=root;;jd^=1,f=son[f][t]) { UP(f,p); if(!jd)t=(p.x<=P[f].x?0:1); else t=(p.y<=P[f].y?0:1); if(!son[f][t]){son[f][t]=v;return ;} } } /* void insert(int &f,Point &p,int jd) //递归版 { if(!f){f=newnode(p);return ;} UP(f,p); int t; if(!jd)t=(p.x<=P[f].x?0:1); else t=(p.y<=P[f].y?0:1); insert(son[f][t],p,!jd); }*/ }kdt; int main() { // freopen("test.in","r",stdin); int i,opt,x,y; scanf("%d%d",&n,&m); for(i=1;i<=n;i++)scanf("%d%d",&P[i].x,&P[i].y); if(n)kdt.root=kdt.build(1,n); while(m--) { scanf("%d%d%d",&opt,&x,&y); int ttt=kdt.cnt+1; P[ttt]=Point(x,y); if(opt==1)kdt.insert(P[ttt],0); else { if(!kdt.root)printf("%d\n",inf); else{ kdt.Mindis=inf; kdt.querymin(kdt.root,P[ttt]); printf("%d\n",kdt.Mindis); } } } return 0; }