题目概述

维护一个点集，有两种操作：1.加入一个点。2.询问 $(x,y)$ 到点集中曼哈顿距离最小值。

解题报告

KDT入门可以看这里。

KDT玄学玩意……我没写重构就过了，写了重构反而TLE了……（反正查距离最小值复杂度本来就不对）

示例程序

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
const int maxn=1000000;
 
int n,m,D,ro,son[maxn+5][2],MN[maxn+5][2],MX[maxn+5][2],ans;
struct Point {int x[2];inline bool operator < (const Point &a) const {return x[D]<a.x[D];}} a[maxn+5];
 
#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> inline int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
inline void Pushup(int p){
    for (int i=0;i<2;i++) MN[p][i]=MX[p][i]=a[p].x[i];
    for (int j=0;j<2;j++)
        for (int i=0;son[p][j]&&i<2;i++)
            MN[p][i]=min(MN[p][i],MN[son[p][j]][i]),MX[p][i]=max(MX[p][i],MX[son[p][j]][i]);
}
int Build(int L,int R,int d=0){
    int m=L+(R-L>>1);D=d;nth_element(a+L,a+m,a+R+1);son[m][0]=son[m][1]=0;
    if (L<m) son[m][0]=Build(L,m-1,d^1);if (m<R) son[m][1]=Build(m+1,R,d^1);Pushup(m);return m;
}
void Insert(int &p,int d=0) {if (!p) return Pushup(p=n);D=d;Insert(son[p][a[p]<a[n]],d^1);Pushup(p);}
#define mindis(p,x,y) (max(MN[p][0]-(x),0)+max((x)-MX[p][0],0)+max(MN[p][1]-(y),0)+max((y)-MX[p][1],0))
inline int absi(int x) {return x<0?-x:x;}
void Ask(int p,int x,int y){
    if (!p) return;ans=min(ans,absi(a[p].x[0]-x)+absi(a[p].x[1]-y));int dis[2]={ans,ans};
    for (int i=0;i<2;i++) if (son[p][i]) dis[i]=mindis(son[p][i],x,y);int d=dis[0]>dis[1];
    if (dis[d]<ans) Ask(son[p][d],x,y);d^=1;if (dis[d]<ans) Ask(son[p][d],x,y);
}
int main(){
    readi(n);readi(m);for (int i=1;i<=n;i++) readi(a[i].x[0]),readi(a[i].x[1]);ro=Build(1,n);
    for (int i=1;i<=m;i++){
        int tp,x,y;readi(tp);readi(x);readi(y);
        if (tp==2) ans=2e9,Ask(ro,x,y),printf("%d\n",ans);
        else n++,a[n].x[0]=x,a[n].x[1]=y,Insert(ro);
    }return 0;
}