题目
平面上有 (N) 个点。需要实现以下三种操作：
-
在点集里添加一个点；
-
给出一个点，查询它到点集里所有点的曼哈顿距离的最小值；
-
给出一个点，查询它到点集里所有点的曼哈顿距离的最大值。
分析
用KD-Tree实现，维护区间横纵坐标最小值和最大值，
由于需要在点集中添加点，可能会导致K-D Tree树高不平衡，
那么直接用替罪羊树拍扁重建即可
代码
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <queue>
#define rr register
using namespace std;
const int N=200011;
typedef long long lll;
const double alp=0.75;
int ran,root,n,m,ans;
inline signed iut(){
rr int ans=0,f=1; rr char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans*f;
}
inline void print(int ans){
if (ans>9) print(ans/10);
putchar(ans%10+48);
}
inline signed min(int a,int b){return a<b?a:b;}
inline signed max(int a,int b){return a>b?a:b;}
struct rec{
int p[2];
bool operator <(const rec &t)const{
return p[ran]<t.p[ran];
}
};
inline signed Abs(int x){return x<0?-x:x;}
struct KD_Tree{
int mn[N][2],mx[N][2],son[N][2],siz[N],stac[N],TOP,tot; rec pt[N],p[N];
inline void pup(int now){
for (rr int i=0;i<2;++i){
mn[now][i]=mx[now][i]=p[now].p[i];
if (son[now][0]){
mn[now][i]=min(mn[now][i],mn[son[now][0]][i]);
mx[now][i]=max(mx[now][i],mx[son[now][0]][i]);
}
if (son[now][1]){
mn[now][i]=min(mn[now][i],mn[son[now][1]][i]);
mx[now][i]=max(mx[now][i],mx[son[now][1]][i]);
}
}
siz[now]=siz[son[now][0]]+siz[son[now][1]]+1;
}
inline bool balance(int now){return alp*siz[now]>=(max(siz[son[now][0]],siz[son[now][1]]));}
inline void recycle(int now){
if (son[now][0]) recycle(son[now][0]);
stac[++TOP]=now,pt[TOP]=p[now];
if (son[now][1]) recycle(son[now][1]);
}
inline signed build(int l,int r,int Ran){
if (l>r) return 0;
rr int mid=(l+r)>>1,now=stac[mid];
ran=Ran,nth_element(pt+l,pt+mid,pt+1+r),p[now]=pt[mid];
son[now][0]=build(l,mid-1,Ran^1);
son[now][1]=build(mid+1,r,Ran^1);
pup(now);
return now;
}
inline void rebuild(int &now,int Ran){
TOP=0,recycle(now);
now=build(1,TOP,Ran);
}
inline void Insert(int &now,rec W,int Ran){
if (!now) now=++tot,p[now]=W;
else{
if (W.p[Ran]<=p[now].p[Ran]) Insert(son[now][0],W,Ran^1);
else Insert(son[now][1],W,Ran^1);
}
pup(now);
if (!balance(now)) rebuild(now,Ran);
}
inline signed calcmn(int t,int x){
rr int ans=0;
for (rr int i=0;i<2;++i) ans+=max(mn[t][i]-p[x].p[i],0)+max(p[x].p[i]-mx[t][i],0);
return ans;
}
inline signed calcmx(int t,int x){
return max(Abs(p[x].p[0]-mn[t][0]),Abs(p[x].p[0]-mx[t][0]))+max(Abs(p[x].p[1]-mn[t][1]),Abs(p[x].p[1]-mx[t][1]));
}
inline void querymn(int now,int x){
rr int t=Abs(p[x].p[0]-p[now].p[0])+Abs(p[x].p[1]-p[now].p[1]);
if (ans>t) ans=t;
rr int c0=calcmn(son[now][0],x),c1=calcmn(son[now][1],x);
if (son[now][0]&&son[now][1]){
if (c0<c1&&c0<ans){
querymn(son[now][0],x);
if (c1<ans) querymn(son[now][1],x);
}else if (c1<ans){
querymn(son[now][1],x);
if (c0<ans) querymn(son[now][0],x);
}
}else if (son[now][0]){
if (c0<ans) querymn(son[now][0],x);
}else if (son[now][1]){
if (c1<ans) querymn(son[now][1],x);
}
}
inline void querymx(int now,int x){
rr int t=Abs(p[x].p[0]-p[now].p[0])+Abs(p[x].p[1]-p[now].p[1]);
if (ans<t) ans=t;
rr int c0=calcmx(son[now][0],x),c1=calcmx(son[now][1],x);
if (son[now][0]&&son[now][1]){
if (c0>c1&&c0>ans){
querymx(son[now][0],x);
if (c1>ans) querymx(son[now][1],x);
}else if (c1>ans){
querymx(son[now][1],x);
if (c0>ans) querymx(son[now][0],x);
}
}else if (son[now][0]){
if (c0>ans) querymx(son[now][0],x);
}else if (son[now][1]){
if (c1>ans) querymx(son[now][1],x);
}
}
}Tre;
signed main(){
n=iut();
for (rr int i=1;i<=n;++i) Tre.Insert(root,(rec){iut(),iut()},0);
for (rr int m=iut();m;--m){
rr int opt=iut(),x,y;
Tre.p[Tre.tot+1].p[0]=x=iut();
Tre.p[Tre.tot+1].p[1]=y=iut();
if (opt==0) Tre.Insert(root,(rec){x,y},0);
else if (opt==1) ans=0x3f3f3f3f,Tre.querymn(root,Tre.tot+1),print(ans),putchar(10);
else ans=-0x3f3f3f3f,Tre.querymx(root,Tre.tot+1),print(ans),putchar(10);
}
return 0;
}