Luogu

分析

KD-Tree 板子。

插入时可能会让 KDT 不平衡,用类似于替罪羊树的方式定期重构即可。

查询时利用到矩形的最短距离剪枝。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=600000+10;
const int inf=0x3f3f3f3f;
const double alpha=0.75;

int n,m;

#define ls t[o].lc
#define rs t[o].rc
int D,rt,sta[N],top=0,tot=0,ans;
struct point { int x[2]; } p[N];
bool operator <(point a,point b) { return a.x[D]<b.x[D]; }
struct node { int mn[2],mx[2],lc,rc,sz; point p; } t[N];
inline int newnode() { return top?sta[top--]:++tot; }
inline void pushup(int o) {
    for (re int i=0;i<2;++i) {
        t[o].mn[i]=t[o].mx[i]=t[o].p.x[i];
        if (ls) {
            t[o].mn[i]=min(t[o].mn[i],t[ls].mn[i]);
            t[o].mx[i]=max(t[o].mx[i],t[ls].mx[i]);
        }
        if (rs) {
            t[o].mn[i]=min(t[o].mn[i],t[rs].mn[i]);
            t[o].mx[i]=max(t[o].mx[i],t[rs].mx[i]);
        }
    }
    t[o].sz=t[ls].sz+t[rs].sz+1;
}
inline int build(int l,int r,int d) {
    if (l>r) return 0;
    int o=newnode(),mid=(l+r)>>1;
    D=d,nth_element(p+l,p+mid,p+r+1),t[o].p=p[mid];
    ls=build(l,mid-1,d^1),rs=build(mid+1,r,d^1);
    pushup(o); return o;
}
inline void rebuild(int o,int pos) {
    if (ls) rebuild(ls,pos);
    p[pos+t[ls].sz+1]=t[o].p,sta[++top]=o;
    if (rs) rebuild(rs,pos+t[ls].sz+1);
}
inline void check(int& o,int d) {
    if (alpha*t[o].sz<max(t[ls].sz,t[rs].sz))
        rebuild(o,0),o=build(1,t[o].sz,d);
}
inline void insert(int& o,point p,int d) {
    if (!o) { o=newnode(); ls=rs=0,t[o].p=p,pushup(o); return; }
    p.x[d]<=t[o].p.x[d]?insert(ls,p,d^1):insert(rs,p,d^1);
    pushup(o); check(o,d);
}
inline int dis(int o,point p) {
    int res=0;
    for (re int i=0;i<2;++i)
        res+=max(p.x[i]-t[o].mx[i],0)+max(t[o].mn[i]-p.x[i],0);
    return res;
}
inline int dis(point a,point b) {
    return abs(a.x[0]-b.x[0])+abs(a.x[1]-b.x[1]);
}
inline void query(int o,point p) {
    ans=min(ans,dis(p,t[o].p));
    int dl=ls?dis(ls,p):inf,dr=rs?dis(rs,p):inf;
    if (dl<dr) {
        if (dl<ans) query(ls,p);
        if (dr<ans) query(rs,p);
    } else {
        if (dr<ans) query(rs,p);
        if (dl<ans) query(ls,p);
    }
}
#undef ls
#undef rs

int main() {
    n=read(),m=read();
    for (re int i=1;i<=n;++i) p[i].x[0]=read(),p[i].x[1]=read();
    rt=build(1,n,0);
    while (m--) { int op; point p;
        op=read(),p.x[0]=read(),p.x[1]=read();
        if (op==1) insert(rt,p,0);
        else ans=inf,query(rt,p),printf("%d\n",ans);
    }
    return 0;
}
最后修改:2020 年 02 月 25 日 11 : 43 AM