K-D树

dim维空间中，维护一堆点，可以快速查询离某个点最近的点。

建树。第a层按照第a%dim维中值分为左子树和右子树， $O(n\log n)$

删除和新增节点。替罪羊树的思路，删除即标记已删除，新增直接插入。不平衡就拆掉这个子树重建。

查询。按照每个点在树节点那一维的左边还是右边，先查那一个子树，再判断全局最小距离比查询点到分界线的距离大，则再查另外一个子树。

#include 
   
    #define endl '\n'#define ls rt << 1#define rs rt << 1 | 1using namespace std;using ll = long long;using pii = pair
    
     ;const int maxn = 2e5 + 5;int k;ll mind;struct ooo{
       int v[2], c, mi, id;    bool operator< (const ooo& ot) const& {
           return v[k] < ot.v[k];    }    friend istream& operator>> (istream &in, ooo &ot){
           in >> ot.v[0] >> ot.v[1] >> ot.c;        ot.mi = ot.c;  // 子树最小c值        return in;    }}data[maxn], tr[maxn<<2], cur, obj;bool leg[maxn<<2]; // 合法点ll dis(const ooo& a, const ooo& b){
       ll ans = 0;    for(int i=0;i<2;++i){
           ans += ll(a.v[i] - b.v[i]) * (a.v[i] - b.v[i]);    }    return ans;  // if need, sqrt}void build(int rt, int l, int r, int dir){
       if(r < l)return;    k = dir;    int mid = l+r>>1;    nth_element(data+l, data+mid, data+r+1);    leg[rt] = true;    tr[rt] = data[mid];    dir = (dir+1)%2;    if(l < mid){
           build(ls, l, mid-1, dir);        tr[rt].mi = min(tr[rt].mi , tr[ls].mi);    }    if(mid < r){
           build(rs, mid+1, r, dir);        tr[rt].mi = min(tr[rt].mi, tr[rs].mi);    }}void query(int rt, int dir){
       if(!leg[rt])return;    if(obj.c < tr[rt].mi)return;    k = dir;    ll d = dis(tr[rt], obj);    if(obj.c >= tr[rt].c){
           if(mind == d && tr[rt].id < cur.id || mind > d){
               cur = tr[rt];            mind = d;        }    }    int son;    if(obj.v[k] < tr[rt].v[k]) son = ls;    else son = rs;    ll val = ll(obj.v[dir]-tr[rt].v[dir]) * (obj.v[dir]-tr[rt].v[dir]);  // 到分界线的直线距离    dir = (dir + 1) % 2;    query(son, dir);    if(val <= mind)        query(son^1, dir);}int main(){
       ios::sync_with_stdio(false);    cin.tie(0), cout.tie(0);    int tt;    cin >> tt;    while(tt--){
           memset(leg, 0, sizeof(leg));        int n, m;        cin >> n >> m;        for(int i=1; i<=n;++i){
               cin >> data[i];            data[i].id = i;        }        build(1, 1, n, 0);        while(m--){
               cin >> obj;            mind = 1e18;            cur.id = maxn;            query(1, 0);            cout << cur.v[0] << ' ' << cur.v[1] << ' ' << cur.c << endl;        }    }}