好久没写博客了 回去赶了好久文化课 颓欲见长
突然翻到fc爷的KD-Tree板子 来切了到裸题
对于一开始的数据我们可以先预处理 具体的排序方式见板子 其实就是我们对每次选定的一块选一个维度来排序啦 这里算了下方差 选最大的那一维来分下去

#include<bits/stdc++.h>

#define bug(x) cout<<(#x)<<" "<<(x)<<endl

#define ll long long

/*

char *TT,*mo,but[(1<<15)+2];

#define getchar() ((TT==mo&&(mo=(TT=but)+fread(but,1,1<<15,stdin),TT==mo))?-1:*TT++)//*/

using namespace std;

const int K=2,N=1e6+5;

inline int read(){

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

struct P{

    int x[K];

}a[N];

struct T{

    int x[K],min[K],max[K],split;

    T *ls,*rs;

}pool[N],*num=pool,*rt;

int cmp_k,ans,n,m,sta,p[K];

bool cmp(P a,P b){

    return a.x[cmp_k]<b.x[cmp_k];

}

void update(T *o,T *x){

    if(!x) return;

    for(int i=0;i<K;i++) o->min[i]=min(o->min[i],x->min[i]),o->max[i]=max(o->max[i],x->max[i]);

}

void build(T *&o,int l,int r){

    if(l>r) {

        o=0;return;

    }

    o=num++;

    int d;double mx=-1;

    for(int i=0;i<K;i++){

        double ave=0,sum=0;

        for(int j=l;j<=r;j++) ave+=a[j].x[i];ave/=r-l+1;

        for(int j=l;j<=r;j++) sum+=(a[j].x[i]-ave)*(a[j].x[i]-ave);

        if(sum>mx) mx=sum,d=i;

    }

    o->split=cmp_k=d;

    int mid=(l+r)>>1;

    nth_element(a+l,a+mid+1,a+r+1,cmp);

    for(int i=0;i<K;i++) o->x[i]=o->min[i]=o->max[i]=a[mid].x[i];

    build(o->ls,l,mid-1),update(o,o->ls);

    build(o->rs,mid+1,r),update(o,o->rs);

}

void insert(T *&o,int kd=0){

    if(!o){

        o=num++;

        o->split=(kd+1)%K;

        for(int i=0;i<K;i++) o->x[i]=o->min[i]=o->max[i]=p[i];

        return;

    }

    for(int i=0;i<K;i++) o->min[i]=min(o->min[i],p[i]),o->max[i]=max(o->max[i],p[i]);

    int d=o->split;

    if(p[d]<o->x[d]) insert(o->ls,d);

    else insert(o->rs,d);

}

void upd(int x){

    ans=min(ans,x);

}

int dist(int *x,int *y){

    int ret=0;

    for(int i=0;i<K;i++) ret+=abs(x[i]-y[i]);

    return ret;

}

int dist(int *x,int *y,int *z){

    int ret=0;

    for(int i=0;i<K;i++)

        if(y[i]>x[i])ret+=y[i]-x[i];

        else if(x[i]>z[i])ret+=x[i]-z[i];

    return ret;

}

void ask(T *o){

    if(!o||dist(p,o->min,o->max)>=ans) return;

    upd(dist(o->x,p));

    int d=o->split;

    if(p[d]<o->x[d]) ask(o->ls),ask(o->rs);

    else ask(o->rs),ask(o->ls);

}

int main(){

#ifdef Devil_Gary

    freopen("in.txt","r",stdin);

#endif

    n=read(),m=read();

    for(int i=1;i<=n;i++) for(int j=0;j<K;j++) a[i].x[j]=read();

    build(rt,1,n);

    while(m--){

        sta=read();

        for(int i=0;i<K;i++) p[i]=read();

        if(sta==2) ans=1<<30,ask(rt),printf("%d\n",ans);

        else insert(rt);

    }

    return 0;

}