解题关键：带插入kdtree模板题。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 1000005
#define inf (1<<30)
using namespace std;
int n,m,dim,rt,ans;
struct node{int p[],x[],y[];}a[N];
bool cmp(node x,node y){ return x.p[dim]<y.p[dim]; }
struct kd_tree{
int c[N][];
node s[N],q;
void update(int k){//管辖范围
int l=c[k][],r=c[k][];
for(int i=;i<;i++){
if(l){ s[k].x[i]=min(s[k].x[i],s[l].x[i]); s[k].y[i]=max(s[k].y[i],s[l].y[i]); }
if(r){ s[k].x[i]=min(s[k].x[i],s[r].x[i]); s[k].y[i]=max(s[k].y[i],s[r].y[i]); }
}
}
void add(int k,node t){ for(int i=;i<;i++)s[k].x[i]=s[k].y[i]=s[k].p[i]=t.p[i]; }
int dist(node t,int k){
int tmp=;
for(int i=;i<;i++) tmp+=max(,s[k].x[i]-t.p[i]);
for(int i=;i<;i++) tmp+=max(,t.p[i]-s[k].y[i]);
return tmp;
}//?
void build(int &k,int l,int r,int now){
k=(l+r)>>; dim=now;
nth_element(a+l,a+k,a+r+,cmp);
add(k,a[k]);
if(l<k) build(c[k][],l,k-,now^);
if(k<r) build(c[k][],k+,r,now^);
update(k);
} void ins(int k,int now){
if(q.p[now]<s[k].p[now]){
if(c[k][]) ins(c[k][],now^);
else c[k][]=++n,add(n,q);
}
else{
if(c[k][]) ins(c[k][],now^);
else c[k][]=++n,add(n,q);
}
update(k);
}
void qry(int k){//曼哈顿距离,且只求最短，dis是最短距离
int tmp=;
for(int i=;i<;i++) tmp+=abs(s[k].p[i]-q.p[i]);
ans=min(ans,tmp);
int dl=c[k][]?dist(q,c[k][]):inf,dr=c[k][]?dist(q,c[k][]):inf;
if(dl<dr){
if(dl<ans) qry(c[k][]);
if(dr<ans) qry(c[k][]);
}else{
if(dr<ans) qry(c[k][]);
if(dl<ans) qry(c[k][]);
}
}
}kd; int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) scanf("%d%d",&a[i].p[],&a[i].p[]);
kd.build(rt,,n,);
while(m--){
int k;
scanf("%d%d%d",&k,&kd.q.p[],&kd.q.p[]);
if(k==) kd.ins(rt,);
else{
ans=inf; kd.qry(rt); printf("%d\n",ans);
}
}
return ;
}
2、将2维普遍化。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 1000005
#define inf (1<<30)
using namespace std;
int n,m,dim,rt,ans,k;
struct node{int p[],minn[],maxx[];}a[N];
bool cmp(node x,node y){ return x.p[dim]<y.p[dim]; }
struct kd_tree{
int c[N][];
node s[N],q;
void update(int o){//管辖范围
int l=c[o][],r=c[o][];
for(int i=;i<k;i++){
if(l){ s[o].minn[i]=min(s[o].minn[i],s[l].minn[i]); s[o].maxx[i]=max(s[o].maxx[i],s[l].maxx[i]); }
if(r){ s[o].minn[i]=min(s[o].minn[i],s[r].minn[i]); s[o].maxx[i]=max(s[o].maxx[i],s[r].maxx[i]); }
}
}
void add(int o,node t){ for(int i=;i<k;i++)s[o].minn[i]=s[o].maxx[i]=s[o].p[i]=t.p[i]; }
int dist(node t,int o){
int tmp=;
for(int i=;i<k;i++) tmp+=max(,s[o].minn[i]-t.p[i]);
for(int i=;i<k;i++) tmp+=max(,t.p[i]-s[o].maxx[i]);
return tmp;
}//?
void build(int &o,int l,int r,int now){
o=(l+r)>>; dim=now%k;
nth_element(a+l,a+o,a+r+,cmp);
add(o,a[o]);
if(l<o) build(c[o][],l,o-,now+);
if(o<r) build(c[o][],o+,r,now+);
update(o);
} void ins(int o,int now){
now%=k;
if(q.p[now]<s[o].p[now]){
if(c[o][]) ins(c[o][],now+);
else c[o][]=++n,add(n,q);
}
else{
if(c[o][]) ins(c[o][],now+);
else c[o][]=++n,add(n,q);
}
update(o);
}
void qry(int o){//曼哈顿距离,且只求最短，dis是最短距离
int tmp=;
for(int i=;i<k;i++) tmp+=abs(s[o].p[i]-q.p[i]);
ans=min(ans,tmp);
int dl=c[o][]?dist(q,c[o][]):inf,dr=c[o][]?dist(q,c[o][]):inf;
if(dl<dr){
if(dl<ans) qry(c[o][]);
if(dr<ans) qry(c[o][]);
}else{
if(dr<ans) qry(c[o][]);
if(dl<ans) qry(c[o][]);
}
}
}kd; int main(){
k=;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) scanf("%d%d",&a[i].p[],&a[i].p[]);
kd.build(rt,,n,);
while(m--){
int k;
scanf("%d%d%d",&k,&kd.q.p[],&kd.q.p[]);
if(k==) kd.ins(rt,);
else{
ans=inf; kd.qry(rt); printf("%d\n",ans);
}
}
return ;
}