k-d Tree

一句话不说你们又不高兴

k-d Tree 可以处理 k 维空间内的最近（第二近、第三近……）邻点查询。

回忆一下二叉搜索树。
每个节点存个值，左子树节点的值都比它小，右子树节点的值都比它大。

问题扩展到 k 维空间内，每个点由一个 k 维向量表示其坐标。
如果树中节点 u 以第 d 维坐标作为分割依据，那么 u 的左子树的第 d 维坐标都比它小，右子树……

这样的树就是 k-d Tree

详情看ppt
注意他那样建树寻址的代价非常小。如果你用全局数组就会t飞2648
所以推荐大家有初始化建树的时候写结构体，否则就写数组或指针吧。结构体飞来飞去太难看了。

闷声写大题

//2648
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cctype>
namespace I {
    const int L = 1 << 15 | 1;
    char *s, *t, buf[L];
    inline char gc() {
        if (s == t) t = (s = buf) + fread(buf, 1, L, stdin);
        return *s++;
    }
    inline int gi() {
        int ch = gc(), x = 0;
        while (!isdigit(ch)) ch = gc();
        while (isdigit(ch)) x = x*10 + ch -'0', ch = gc();
        return x;
    }
}using I::gi;
using std::max;
using std::min;
const int N = int(5e5 + 10) << 1;
const double fac = 0.7;
int n, m, D, mem, rt;
struct ND {
    int d[2], mn[2], mx[2], ch[2];
    bool operator<(const ND& b)const {return d[D] < b.d[D];}
    inline void rd() {
        d[0] = gi(), d[1] = gi();
    }
}a[N];
inline void up(int o) {
    for (int i = 0; i < 2; i++) {
        a[o].mn[i] = a[o].mx[i] = a[o].d[i];
        for (int j = 0; j < 2; j++) if (a[o].ch[j]) {
            a[o].mn[i] = min(a[o].mn[i], a[a[o].ch[j]].mn[i]);
            a[o].mx[i] = max(a[o].mx[i], a[a[o].ch[j]].mx[i]);
        }
    }
}
int build(int l, int r, int t) {
    if (l > r) return 0;
    int mid = l + r >> 1;
    D = t;
    std::nth_element(a + l, a + mid, a + r + 1);
    a[mid].ch[0] = build(l, mid - 1, t^1);
    a[mid].ch[1] = build(mid + 1, r, t^1);
    up(mid);
    return mid;
}
void in(int& o, int p, int t) {
    if (!o) o = p;
    else in(a[o].ch[a[p].d[t] > a[o].d[t]], p, t^1);
    up(o);
}
int x, y, ans;
inline int val(int o) {
    return o ? max(max(a[o].mn[0] - x, x - a[o].mx[0]), 0) + max(max(a[o].mn[1] - y, y - a[o].mx[1]), 0): 1e9;
}
void query(int o) {
    if (!o) return;
    ans = min(abs(a[o].d[0] - x) + abs(a[o].d[1] - y), ans);
    int gd[2];
    gd[0] = val(a[o].ch[0]), gd[1] = val(a[o].ch[1]);
    int t = gd[1] < gd[0];
    if (gd[t] < ans) query(a[o].ch[t]);
    t^=1;
    if (gd[t] < ans) query(a[o].ch[t]);
}
int main() {
    n = gi(), m = gi();
    for (int i = 1; i <= n; i++) {
        a[++mem].rd();
        up(i);
    }
    rt = build(1, mem, 0);
    while (m--) {
        int t = gi();
        x = gi(), y = gi();
        if (t == 1) {
            ++mem;
            a[mem].d[0] = x, a[mem].d[1] = y;
            up(mem);
            in(rt, mem, 0);
        }
        else if (t == 2) {
            ans = 1e9;
            query(rt);
            printf("%d\n", ans);
        }
    }
}

//4066
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
const double fac = 0.7;
int n, m, D, ans, sz;
struct ND{
    int d[2], l[2], r[2], sz, w, s;
    ND* ch[2];
    ND(int x, int y, int v) {d[0] = x, d[1] = y, w = v;up();}
    inline void up() {
        l[0] = r[0] = d[0];
        l[1] = r[1] = d[1];
        s = w;
        sz = 1;
        for (int j = 0; j < 2; j++) if (ch[j]) {
            s += ch[j]->s;
            sz += ch[j]->sz;
            for (int i = 0; i < 2; i++)
                l[i] = std::min(l[i], ch[j]->l[i]),
                r[i] = std::max(r[i], ch[j]->r[i]);
        }
    }
}*rt;
bool cmp(ND* a, ND* b) {
    return a->d[D] < b->d[D];
}
ND* po[int(5e5 + 1) << 2];
ND* build(int l, int r, int d) {
    if (l > r) return 0;
    D = d;
    int mid = l + r >> 1;
    std::nth_element(po + l, po + mid, po + r + 1, cmp);
    ND* p = po[mid];
    p->ch[0] = build(l, mid - 1, d^1);
    p->ch[1] = build(mid + 1, r, d^1);
    p->up();
    return p;
}
void dfs(ND* u) {
    if (!u) return;
    dfs(u->ch[0]);
    po[++sz] = u;
    dfs(u->ch[1]);
}
void rebuild(ND*& u, int d) {
    sz = 0;
    dfs(u);
    u = build(1, sz, d);
}
void in(ND*& o, ND* p, int d) {
    if (!o) o = p;
    else in(o->ch[p->d[d] >= o->d[d]], p, d^1);
    o->up();
    int s = 0;
    for (int i = 0; i < 2; i++) if (o->ch[i]) s = std::max(s, o->ch[i]->sz);
    if (s > o->sz*fac) rebuild(o, d);
}
int x0, x1, y0, y1;
int query(ND* o) {
    if (!o || o->l[0] > x1 || o->r[0] < x0 || o->l[1] > y1 || o->r[1] < y0) return 0;
    if (x0 <= o->l[0] && o->r[0] <= x1 &&
            y0 <= o->l[1] && o->r[1] <= y1) return o->s;
    int s = 0;
    if (x0 <= o->d[0] && o->d[0] <= x1 &&
            y0 <= o->d[1] && o->d[1] <= y1) s += o->w;
    return s + query(o->ch[0]) + query(o->ch[1]);
}
int main() {
//  freopen("input", "r", stdin);
//  freopen("bzoj_4066.in", "r", stdin);
//  freopen("bzoj_4066.out", "w", stdout);
    scanf("%d", &n);
    while (1) {
        int t;
        scanf("%d", &t);
        if (t == 1) {
            int x, y, w;
            scanf("%d%d%d", &x, &y, &w);
            x^=ans, y^=ans, w^=ans;
            ND* p = new ND(x, y, w);
            in(rt, p, 0);
        }
        else if (t == 2) {
            scanf("%d%d%d%d", &x0, &y0, &x1, &y1);
            x0 ^= ans, x1^=ans, y0^=ans,y1^=ans;
            printf("%d\n", ans = query(rt));
        }
        else break;
    }
}

//3053
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cassert>
#define nxd ((d + 1)%k)
using std::min;
using std::max;
const int N = 5e4 + 10, K = 5, M = 15, INF = 2e9 + 1;
int n, D, k, m, ans[M];
struct P{
    int d[K], mn[K], mx[K], ch[2];
    bool operator<(const P& b)const {return d[D] < b.d[D];}
    inline void rd() {
        for (int i = 0; i < k; i++) scanf("%d", &d[i]);
    }
}a[N];
inline void up(int o) {
    for (int i = 0; i < k; i++) a[o].mn[i] = a[o].mx[i] = a[o].d[i];
    for (int i = 0; i < 2; i++) if (a[o].ch[i])
        for (int j = 0; j < k; j++) a[o].mn[j] = min(a[o].mn[j], a[a[o].ch[i]].mn[j]), a[o].mx[j] = max(a[o].mx[j], a[a[o].ch[i]].mx[j]);
}
inline int sq(int x) {return x*x;}
inline int dis(int x, int y) {
    if (!x || !y) return INF;
    int s = 0;
    for (int i = 0; i < k; i++) s += sq(a[x].d[i] - a[y].d[i]);
    return s;
}
int build(int l, int r, int d) {
    if (l > r) return 0;
    int mid = l + r >> 1;
    D = d;
    std::nth_element(a + l, a + mid, a + r + 1);
    a[mid].ch[0] = build(l, mid - 1, nxd);
    a[mid].ch[1] = build(mid + 1, r, nxd);
    up(mid);
    return mid;
}
int acnt;
inline void addans(int o) {
    int dd = dis(o, n + 1);
    for (int i = 1; i <= min(acnt + 1, m); i++) if (dd < dis(ans[i], n + 1)) {
        for (int j = acnt; j > i; j--) ans[j] = ans[j - 1];
        ans[i] = o;
        acnt = min(acnt + 1, m);
        break;
    }
//  for (int i = 1; i < acnt; i++) assert(dis(ans[i], n + 1) < dis(ans[i + 1], n + 1));
}
inline int val(int o) {
    if (o) {
        int s = 0;
        for (int i = 0, c = n + 1; i < k; i++) s += sq(max(max(a[o].mn[i] - a[c].d[i], a[c].d[i] - a[o].mx[i]), 0));
        return s;
    }
    else return INF;
}
void query(int o) {
    if (!o) return;
    addans(o);
    int gd[2];
    gd[0] = val(a[o].ch[0]), gd[1] = val(a[o].ch[1]);
    int t = gd[1] < gd[0], dd = dis(ans[m], n + 1);
    if (dd >= gd[t]) query(a[o].ch[t]);
    t ^= 1;
    dd = dis(ans[m], n + 1);
    if (dd >= gd[t]) query(a[o].ch[t]);
}
int rt;
void solve() {
    for (int i = 1; i <= n; i++) a[i].rd(), up(i);
    rt = build(1, n, 0);
    int q;
    scanf("%d", &q);
    while (q--) {
        for (int i = 0; i < k; i++) scanf("%d", &a[n + 1].d[i]);
        scanf("%d", &m);
        memset(ans, 0, sizeof(ans));
        acnt = 0;
        query(rt);
        printf("the closest %d points are:\n", m);
        for (int i = 1; i <= m; i++) {
            for (int j = 0; j < k; j++) printf("%d", a[ans[i]].d[j]), j == k - 1 ? 0: putchar(' ');
            putchar('\n');
        }
    }
}
int main() {
    //freopen("input", "r", stdin);
    while (scanf("%d%d", &n, &k) == 2) solve();
}