一句话不说你们又不高兴
k-d Tree 可以处理 k 维空间内的最近（第二近、第三近……）邻点查询。
回忆一下二叉搜索树。
每个节点存个值，左子树节点的值都比它小，右子树节点的值都比它大。
问题扩展到 k 维空间内，每个点由一个 k 维向量表示其坐标。
如果树中节点 u 以第 d 维坐标作为分割依据，那么 u 的左子树的第 d 维坐标都比它小，右子树……
这样的树就是 k-d Tree
详情看ppt
注意他那样建树寻址的代价非常小。如果你用全局数组就会t飞2648
所以推荐大家有初始化建树的时候写结构体，否则就写数组或指针吧。结构体飞来飞去太难看了。
闷声写大题
| Prob | Hint |
|---|---|
| 2648-SJY摆棋子 | kdtree 不需要重建 |
| 4066-简单题 | kdtree 区域查询 需要重建 |
| 3053-The-Closet-M-Points | 真k dtree，不带修改 |
//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();
}