KD树学习小结

几个月后的UPD:

学习完下面之后，实战中的总结:

0.比赛中正解就是kdtree的题目很少很少

1.几类优先考虑kdtree的题目：

　　k(维度) >= 3 的题目

　　二维平面上涉及区间标记的题目

2. 二维平面上的题目， n >= 5W 谨慎使用kdtree

非强制在线考虑cdq套数据结构(不涉及标记的话基本考虑树状数组)

强制在线考虑树状数组套主席树(该方法需要提前确定空间够不够O(nlogn2))

　 几种方法的常数比较:cdq套树 < 树套树 < kdtree

　编程复杂度也是cdq最小，后面两个差不多

3.非写kdtree不可的题目，常数上的几个优化

　<0>快速读入，快速输出的话，不超过50W的个数基本没必要

　<1>重构kdtree的参数选择，插入多查询少的情况，最优参数是接近 0.5 + x / (x + y) 的

　　 x是插入个数，y是查询个数

插入少查询多的话，最优参数其实是更接近 0.7 + x / (x + y) 的，查询再多也不建议参数低于0.7

　　 当然最优参数的话，有时间可以自己去测试调整

　<2>其实update函数那里吧两个 if 直接写成 max / min 未必时间会差一点，可以自己尝试测试时间

学习资料在这里

对于k维KDTree，实际时间复杂度为O(N*N^(1-1/k))

build实现类似spaly，不断选一维从中间划分，可以循环选取维度，也可以rand % k

求最近点的query，重点在于其中的估价函数

求区间和的query，则和线段树类似

例题：

1) bzoj 2648求最近点

  1 /*为了维持树的平衡，可以一开始把所有点都读进来build
  2 然后打flag标记该点是否被激活*/
  3 #include <bits/stdc++.h>
  4 
  5 using namespace std;
  6 
  7 const int N = 5e5 + 5;
  8 
  9 const int inf = 1 << 30;
 10 
 11 int n, m;
 12 
 13 int ql, qr, ans, tot, nowD;
 14 //nowD = rand() & 1 ?
 15 struct Node {
 16     int d[2];
 17 
 18     bool operator < (const Node &a) const {
 19         if (d[nowD] == a.d[nowD]) return d[!nowD] < a.d[!nowD];
 20         return d[nowD] < a.d[nowD];
 21     }
 22 }pot[N];
 23 
 24 struct node {
 25     int min[2], max[2], d[2];
 26     node *c[2];
 27 
 28     node() {
 29         min[0] = min[1] = max[0] = max[1] = d[0] = d[1] = 0;
 30         c[0] = c[1] = NULL;
 31     }
 32 
 33     node(int x, int y);
 34 
 35     void update();
 36 
 37     
 38 }t[N], Null, *root;
 39 
 40 node::node(int x, int y) {
 41     min[0] = max[0] = d[0] = x;
 42     min[1] = max[1] = d[1] = y;
 43     c[0] = c[1] = &Null;
 44 }
 45 
 46 inline void node::update() {
 47     if (c[0] != &Null) {
 48         if (c[0] -> max[0] > max[0]) max[0] = c[0] -> max[0];
 49         if (c[0] -> max[1] > max[1]) max[1] = c[0] -> max[1];
 50         if (c[0] -> min[0] < min[0]) min[0] = c[0] -> min[0];
 51         if (c[0] -> min[1] < min[1]) min[1] = c[0] -> min[1];
 52     }
 53     if (c[1] != &Null) {
 54         if (c[1] -> max[0] > max[0]) max[0] = c[1] -> max[0];
 55         if (c[1] -> max[1] > max[1]) max[1] = c[1] -> max[1];
 56         if (c[1] -> min[0] < min[0]) min[0] = c[1] -> min[0];
 57         if (c[1] -> min[1] < min[1]) min[1] = c[1] -> min[1];
 58     }
 59 }
 60 
 61 inline void build(node *&o, int l, int r, int D) {
 62     int mid = l + r >> 1;
 63     nowD = D;
 64     nth_element(pot + l, pot + mid, pot + r + 1);
 65     o = new node(pot[mid].d[0], pot[mid].d[1]);
 66 
 67     if (l != mid) build(o -> c[0], l, mid - 1, !D);
 68     if (r != mid) build(o -> c[1], mid + 1, r, !D);
 69     o -> update();
 70 }
 71 
 72 inline void insert(node *o) {
 73     node *p = root;
 74     int D = 0;
 75     while (1) {
 76         if (o -> max[0] > p -> max[0]) p -> max[0] = o -> max[0];
 77         if (o -> max[1] > p -> max[1]) p -> max[1] = o -> max[1];
 78         if (o -> min[0] < p -> min[0]) p -> min[0] = o -> min[0];
 79         if (o -> min[1] < p -> min[1]) p -> min[1] = o -> min[1];
 80 
 81         if (o -> d[D] >= p -> d[D]) {
 82             if (p -> c[1] == &Null) {
 83                 p -> c[1] = o;
 84                 return;
 85             } else p = p -> c[1];
 86         } else {
 87             if (p -> c[0] == &Null) {
 88                 p -> c[0] = o;
 89                 return;
 90             } else p = p -> c[0];
 91         }
 92         D ^= 1;
 93     } 
 94 }
 95 
 96 inline int dist(node *o) {
 97     int dis = 0;
 98     if (ql < o -> min[0]) dis += o -> min[0] - ql;
 99     if (ql > o -> max[0]) dis += ql - o -> max[0];
100     if (qr < o -> min[1]) dis += o -> min[1] - qr;
101     if (qr > o -> max[1]) dis += qr - o -> max[1];
102     return dis; 
103 }
104 
105 inline void query(node *o) {
106     int dl, dr, d0;
107     d0 = abs(o -> d[0] - ql) + abs(o -> d[1] - qr);
108     if (d0 < ans) ans = d0;
109     if (o -> c[0] != &Null) dl = dist(o -> c[0]);
110     else dl = inf;
111     if (o -> c[1] != &Null) dr = dist(o -> c[1]);
112     else dr = inf;
113 
114     if (dl < dr) {
115         if (dl < ans) query(o -> c[0]);
116         if (dr < ans) query(o -> c[1]);
117     } else {
118         if (dr < ans) query(o -> c[1]);
119         if (dl < ans) query(o -> c[0]);
120     }
121 }
122 
123 int main() {
124     ios::sync_with_stdio(false);
125     cin >> n >> m;
126     for (int i = 1; i <= n; i ++)
127         cin >> pot[i].d[0] >> pot[i].d[1];
128     build(root, 1, n, 0);
129     
130     for (int x, y, z; m --; ) {
131         cin >> x >> y >> z;
132         if (x == 1) {
133             t[tot].max[0] = t[tot].min[0] = t[tot].d[0] = y;
134             t[tot].max[1] = t[tot].min[1] = t[tot].d[1] = z;
135             t[tot].c[0] = t[tot].c[1] = &Null;
136             insert(&t[tot ++]);
137         } else {
138             ans = inf, ql = y, qr = z;
139             query(root), printf("%d
", ans);
140         }
141     }
142     return 0;
143 }

View Code

3种写法可选

<1>插入的时候采用替罪羊树的方法来维护，子树太偏就直接重构

<2>一开始直接把所有点扔进kdtree，用flag来标记该点是否被激活

<3>直接插入不重构。事实上本题没有出极端数据导致树会特别偏，所以可过。这种写法需要稍稍注意常数

2) bzoj 4066 二维平面，单点修改，区间查询，强制在线

  1 #include <bits/stdc++.h>
  2  
  3 using namespace std;
  4  
  5 const int inf = 1e9;
  6  
  7 int n, m, tot, nowD;
  8  
  9 struct node {
 10     int Max[2], Min[2], d[2];
 11     int sum, siz, val;
 12     node *c[2];
 13  
 14     node() {
 15         Max[0] = Max[1] = -inf;
 16         Min[0] = Min[1] = inf;
 17         sum = val = siz = 0;
 18         c[0] = c[1] = NULL;
 19         d[0] = d[1] = 0;
 20     }
 21  
 22     void update();
 23 }Null, nodes[200010], *temp[200010];
 24  
 25 node *root = &Null;
 26  
 27 inline void node::update() {
 28     siz = c[0] -> siz + c[1] -> siz + 1;
 29     sum = c[0] -> sum + c[1] -> sum + val;
 30     if (c[0] != &Null) {
 31         if (c[0] -> Max[0] > Max[0]) Max[0] = c[0] -> Max[0];
 32         if (c[0] -> Max[1] > Max[1]) Max[1] = c[0] -> Max[1];
 33         if (c[0] -> Min[0] < Min[0]) Min[0] = c[0] -> Min[0];
 34         if (c[0] -> Min[1] < Min[1]) Min[1] = c[0] -> Min[1];
 35     }
 36     if (c[1] != &Null) {
 37         if (c[1] -> Max[0] > Max[0]) Max[0] = c[1] -> Max[0];
 38         if (c[1] -> Max[1] > Max[1]) Max[1] = c[1] -> Max[1];
 39         if (c[1] -> Min[0] < Min[0]) Min[0] = c[1] -> Min[0];
 40         if (c[1] -> Min[1] < Min[1]) Min[1] = c[1] -> Min[1];
 41     }
 42 }
 43  
 44 inline bool cmp(const node *a, const node *b) {
 45     return a -> d[nowD] < b -> d[nowD];
 46 }
 47  
 48 inline void traverse(node *o) {
 49     if (o == &Null) return;
 50     temp[++ tot] = o;
 51     traverse(o -> c[0]);
 52     traverse(o -> c[1]);
 53 }
 54  
 55 inline node *build(int l, int r, int D) {
 56     int mid = l + r >> 1; nowD = D;
 57     nth_element(temp + l, temp + mid, temp + r + 1, cmp);
 58     node *res = temp[mid];
 59     res -> Max[0] = res -> Min[0] = res -> d[0];
 60     res -> Max[1] = res -> Min[1] = res -> d[1];
 61     if (l != mid) res -> c[0] = build(l, mid - 1, !D);
 62     else res -> c[0] = &Null;
 63     if (r != mid) res -> c[1] = build(mid + 1, r, !D);
 64     else res -> c[1] = &Null;
 65     res -> update();
 66     return res;
 67 }
 68  
 69 int x, y, a, b, tmpD;
 70  
 71 node **tmp;
 72  
 73 inline void rebuild(node *&o, int D) {
 74     tot = 0;
 75     traverse(o);
 76     o = build(1, tot, D);
 77 }
 78  
 79 inline void insert(node *&o, node *p, int D) {
 80     if (o == &Null) {o = p; return;}
 81     if (p -> Max[0] > o -> Max[0]) o -> Max[0] = p -> Max[0];
 82     if (p -> Max[1] > o -> Max[1]) o -> Max[1] = p -> Max[1];
 83     if (p -> Min[0] < o -> Min[0]) o -> Min[0] = p -> Min[0];
 84     if (p -> Min[1] < o -> Min[1]) o -> Min[1] = p -> Min[1];
 85     o -> siz ++, o -> sum += p -> sum;
 86     insert(o -> c[p -> d[D] >= o -> d[D]], p, !D);
 87     if (max(o -> c[0] -> siz, o -> c[1] -> siz) > int(o -> siz * 0.75 + 0.5)) tmpD = D, tmp = &o;
 88 }
 89  
 90 inline int query(node *o, int D) {
 91     if (o == &Null) return 0;
 92     if (x > o -> Max[0] || y > o -> Max[1] || a < o -> Min[0] || b < o -> Min[1]) return 0;
 93     if (x <= o -> Min[0] && y <= o -> Min[1] && a >= o -> Max[0] && b >= o -> Max[1]) return o -> sum;
 94     return (x <= o -> d[0] && y <= o -> d[1] && a >= o -> d[0] && b >= o -> d[1] ? o -> val : 0) 
 95         + query(o -> c[1], !D) + query(o -> c[0], !D);
 96 }
 97  
 98 int main() {
 99     ios::sync_with_stdio(false);
100     cin >> m;
101     node *ttt = &Null;
102     for (int t, ans = 0; ; ) {
103         cin >> t;
104         if (t == 3) break;
105         if (t == 1) {
106             cin >> x >> y >> a;
107             x ^= ans, y ^= ans, n ++;
108             nodes[n].sum = nodes[n].val = a ^ ans, nodes[n].siz = 1;
109             nodes[n].Max[0] = nodes[n].Min[0] = nodes[n].d[0] = x;
110             nodes[n].Max[1] = nodes[n].Min[1] = nodes[n].d[1] = y;
111             nodes[n].c[0] = nodes[n].c[1] = &Null;
112             tmp = &(ttt), insert(root, &nodes[n], 0);
113             if (*tmp != &Null) rebuild(*tmp, tmpD); 
114         } else {
115             cin >> x >> y >> a >> b;
116             x ^= ans, y ^= ans, a ^= ans, b ^= ans;
117             if (x > a) swap(x, a);
118             if (y > b) swap(y, b);
119             ans = query(root, 0);
120             printf("%d
", ans);
121         }
122     }
123     return 0;
124 }

View Code

正直写法，子树size过大就要Rebuild

判断rebuild的系数取的0.75，注意rebuild不是在回溯过程中当前子树不平衡就立刻重构

而是回溯过程中找到最靠近根的需要重构的子树根节点，然后对这棵树进行重构

详情看代码

不正直写法，新节点先存在数组里，查询时遍历该数组+查询kdtree

当数组size大于K时，把数组里的点放进kdtree并重构整颗kdtree

K取10000即可，可过

3) bzoj4154 二维平面，区间覆盖，单点查询

  1 #include <bits/stdc++.h>
  2 
  3 using namespace std;
  4 
  5 const int N = 1e5 + 5;
  6 
  7 const int Mod = 1e9 + 7;
  8 
  9 int nowD, x[2], y[2], z;
 10 
 11 struct node {
 12     int Max[2], Min[2], d[2];
 13     int val, lazy;
 14     node *c[2];
 15 
 16     node() {
 17         c[0] = c[1] = NULL;
 18     }
 19 
 20     void pushup();
 21 
 22     void pushdown();
 23 
 24     bool operator < (const node &a) const {
 25         return d[nowD] < a.d[nowD];
 26     }
 27 }Null, nodes[N];
 28 
 29 node *root = &Null;
 30 
 31 inline void node::pushup() {
 32     if (c[0] != &Null) {
 33         if (c[0] -> Max[0] > Max[0]) Max[0] = c[0] -> Max[0];
 34         if (c[0] -> Max[1] > Max[1]) Max[1] = c[0] -> Max[1];
 35         if (c[0] -> Min[0] < Min[0]) Min[0] = c[0] -> Min[0];
 36         if (c[0] -> Min[1] < Min[1]) Min[1] = c[0] -> Min[1];
 37     }
 38     if (c[1] != &Null) {
 39         if (c[1] -> Max[0] > Max[0]) Max[0] = c[1] -> Max[0];
 40         if (c[1] -> Max[1] > Max[1]) Max[1] = c[1] -> Max[1];
 41         if (c[1] -> Min[0] < Min[0]) Min[0] = c[1] -> Min[0];
 42         if (c[1] -> Min[1] < Min[1]) Min[1] = c[1] -> Min[1];
 43     }
 44 }
 45 
 46 inline void node::pushdown() {
 47     if (c[0] != &Null) c[0] -> val = c[0] -> lazy = lazy;
 48     if (c[1] != &Null) c[1] -> val = c[1] -> lazy = lazy;
 49     lazy = -1;
 50 }
 51 
 52 inline node *build(int l, int r, int D) {
 53     int mid = l + r >> 1; nowD = D;
 54     nth_element(nodes + l, nodes + mid, nodes + r + 1);
 55     node *res = &nodes[mid];
 56     if (l != mid) res -> c[0] = build(l, mid - 1, !D);
 57     else res -> c[0] = &Null;
 58     if (r != mid) res -> c[1] = build(mid + 1, r, !D);
 59     else res -> c[1] = &Null;
 60     res -> pushup();
 61     return res;
 62 }
 63 
 64 inline int query(node *o) {
 65     if (o == &Null) return -1;
 66     if (o -> lazy != -1) o -> pushdown();
 67     if (x[0] > o -> Max[0] || y[0] > o -> Max[1] || x[0] < o -> Min[0] || y[0] < o -> Min[1]) return -1;
 68     if (x[0] == o -> d[0]) return o -> val;
 69     return max(query(o -> c[0]), query(o -> c[1]));
 70 }
 71 
 72 inline void modify(node *o) {
 73     if (o == &Null) return;
 74     if (o -> lazy != -1) o -> pushdown();
 75     if (x[0] > o -> Max[0] || y[0] > o -> Max[1] || x[1] < o -> Min[0] || y[1] < o -> Min[1]) return;
 76     if (x[0] <= o -> Min[0] && y[0] <= o -> Min[1] && x[1] >= o -> Max[0] && y[1] >= o -> Max[1]) {
 77         o -> val = o -> lazy = z;
 78         return;
 79     }
 80     if (x[0] <= o -> d[0] && y[0] <= o -> d[1] && x[1] >= o -> d[0] && y[1] >= o -> d[1]) o -> val = z;
 81     modify(o -> c[0]), modify(o -> c[1]);
 82 }
 83 
 84 int n, m, k, a[N], c[N], d[N];
 85 
 86 int cnt, st[N], en[N], dfn[N], dep[N];
 87 
 88 vector <int> e[N];
 89 
 90 void dfs(int u) {
 91     st[u] = ++ cnt, dfn[cnt] = u;
 92     for (int v : e[u])
 93         dep[v] = dep[u] + 1, dfs(v);
 94     en[u] = cnt;
 95 }
 96 
 97 int main() {
 98     ios::sync_with_stdio(false);
 99     int T, ans;
100     for (cin >> T; T --; ) {
101         cin >> n >> m >> k, ans = cnt = 0;
102         for (int i = 1; i <= n; i ++)
103             e[i].clear();
104         for (int u, i = 2; i <= n; i ++) {
105             cin >> u;
106             e[u].push_back(i);
107         }
108         dfs(1);
109         for (int i = 1; i <= n; i ++) {
110             nodes[i].Min[0] = nodes[i].Max[0] = nodes[i].d[0] = i;
111             nodes[i].Min[1] = nodes[i].Max[1] = nodes[i].d[1] = dep[dfn[i]];
112             nodes[i].val = 1, nodes[i].lazy = -1;
113         }
114         root = build(1, n, 0);
115         for (int u, v, w, i = 1; i <= k; i ++) {
116             cin >> u >> v >> w;
117             if (w == 0) {
118                 x[0] = st[u], y[0] = dep[u];
119                 ans = (ans + 1ll * i * query(root) % Mod) % Mod;
120             } else {
121                 x[0] = st[u], x[1] = en[u];
122                 y[0] = dep[u], y[1] = dep[u] + v;
123                 z = w, modify(root);
124             }
125         }
126         cout << ans << endl;
127     }
128     return 0;
129 }

View Code

重点在于观察到修改的是一定距离以内的子节点

所以考虑转换到二维平面，一维为dfs序，一维为dep

通过子树区间+深度区间限制，即可得到修改的点集

二维平面上区间覆盖+单点查询，kdtree即可

4) bzoj3489 求区间内最大的只出现过一次的数

  1 #include <bits/stdc++.h>
  2 
  3 using namespace std;
  4 
  5 const int N = 1e5 + 5;
  6 
  7 const int Mod = 1e9 + 7;
  8 
  9 int nowD, ans, x[3], y[3];
 10 
 11 int n, m, a[N], b[N], c[N], d[N];
 12 
 13 struct node {
 14     int Max[3], Min[3], d[3];
 15     int val, maxv;
 16     node *c[2];
 17 
 18     node() {
 19         c[0] = c[1] = NULL;
 20         val = maxv = 0;
 21     }
 22 
 23     void pushup();
 24 
 25     bool operator < (const node &a) const {
 26         return d[nowD] < a.d[nowD];
 27     }
 28 }Null, nodes[N];
 29 
 30 node *root = &Null;
 31 
 32 inline void node::pushup() {
 33     if (c[0] != &Null) {
 34         if (c[0] -> Max[1] > Max[1]) Max[1] = c[0] -> Max[1];
 35         if (c[0] -> Max[2] > Max[2]) Max[2] = c[0] -> Max[2];
 36         if (c[0] -> Min[0] < Min[0]) Min[0] = c[0] -> Min[0];
 37         if (c[0] -> Min[2] < Min[2]) Min[2] = c[0] -> Min[2];
 38         if (c[0] -> maxv > maxv) maxv = c[0] -> maxv;
 39     }
 40     if (c[1] != &Null) {
 41         if (c[1] -> Max[1] > Max[1]) Max[1] = c[1] -> Max[1];
 42         if (c[1] -> Max[2] > Max[2]) Max[2] = c[1] -> Max[2];
 43         if (c[1] -> Min[0] < Min[0]) Min[0] = c[1] -> Min[0];
 44         if (c[1] -> Min[2] < Min[2]) Min[2] = c[1] -> Min[2];
 45         if (c[1] -> maxv > maxv) maxv = c[1] -> maxv;
 46     }
 47 }
 48 
 49 inline node *build(int l, int r) {
 50     int mid = l + r >> 1; nowD = rand() % 3;
 51     nth_element(nodes + l, nodes + mid, nodes + r + 1);
 52     node *res = &nodes[mid];
 53     if (l != mid) res -> c[0] = build(l, mid - 1);
 54     else res -> c[0] = &Null;
 55     if (r != mid) res -> c[1] = build(mid + 1, r);
 56     else res -> c[1] = &Null;
 57     res -> pushup();
 58     return res;
 59 }
 60 
 61 inline int calc(node *o) {
 62     if (y[0] < o -> Min[0] || x[1] > o -> Max[1] || x[2] > o -> Max[2] || y[2] < o -> Min[2]) return -1;
 63     return o -> maxv;
 64 }
 65 
 66 inline void query(node *o) {
 67     if (o -> val > ans && y[0] >= o -> d[0] && x[1] <= o -> d[1] && x[2] <= o -> d[2] && y[2] >= o -> d[2]) ans = o -> val;
 68     int dl, dr;
 69     if (o -> c[0] != &Null) dl = calc(o -> c[0]);
 70     else dl = -1;
 71     if (o -> c[1] != &Null) dr = calc(o -> c[1]);
 72     else dr = -1;
 73     if (dl > dr) {
 74         if (dl > ans) query(o -> c[0]);
 75         if (dr > ans) query(o -> c[1]);
 76     } else {
 77         if (dr > ans) query(o -> c[1]);
 78         if (dl > ans) query(o -> c[0]);
 79     }
 80 
 81 }
 82 
 83 int main() {
 84     ios::sync_with_stdio(false);
 85     cin >> n >> m;
 86     for (int i = 1; i <= n; i ++) {
 87         cin >> a[i];
 88         b[i] = d[a[i]];
 89         d[a[i]] = i;
 90     }
 91     for (int i = 1; i <= n; i ++) d[i] = n + 1;
 92     for (int i = n; i; i --) {
 93         c[i] = d[a[i]];
 94         d[a[i]] = i;
 95     }
 96     for (int i = 1; i <= n; i ++) {
 97         nodes[i].Min[0] = nodes[i].d[0] = b[i];
 98         nodes[i].Max[1] = nodes[i].d[1] = c[i];
 99         nodes[i].Max[2] = nodes[i].Min[2] = nodes[i].d[2] = i;
100         nodes[i].val = nodes[i].maxv = a[i];
101     }
102     root = build(1, n);
103     for (int l, r; m --; ) {
104         cin >> l >> r;
105         l = (l + ans) % n + 1;
106         r = (r + ans) % n + 1;
107         if (l > r) swap(l, r);
108         y[0] = l - 1;
109         x[1] = r + 1;
110         x[2] = l, y[2] = r;
111         ans = 0, query(root);
112         cout << ans << endl;
113     }
114     cout << endl;
115     return 0;
116 }

View Code

考虑a[i]上一次出现，和下一次出现位置分别pre[i], suc[i]

即变成pre[i], i, suc[i]在[0, l - 1], [l, r], [r + 1, n + 1]之间的数的最大值

3维KDtree即可，注意也要使用ans与区间最值的关系来优化

注意到3维有不需要的变量，不需要维护，40s时限跑了39s+...

简单总结:

1) 解决求最值的问题，kdtree其实就是优化暴力，所以一般都需要估价函数优化才可以

2) 非最值问题，其实感觉更像线段树，但由于奇妙的原因，所以一次更新覆盖到的区间可能达到O(sqrt(n))个

3) 由于本质是暴力，所以常数比较重要，inline，子树非空才更新，估价函数，无用信息不更新...各种优化,一般而言10W已经是极限

4) 板子题不说, KDtree的题目需要从题中找到k维平面,然后区间修改和区间查询就完事了

5) 非强制在线题目,并不优先考虑kdtree,可以考虑树套树,kdtree不强制在线可以考虑排序降维

其他例题

5) bzoj4520 给N个点,求第K远点对

solution:可以看到k比较小,所以所有点建好kdtree,对每个点查询一下,维护出一个大小为k的堆

把n个点的堆进行合并,和并出大小为2k的堆,即得到答案

6) hdu 5992

可以考虑裸的3维kdtree,能过

考虑到n比较大,不强制在线,可以按价格排序,带插入的kdtree,需要重构

这个题我打训练赛写后一种排序重构写法T到自闭

然后把那个重构的参数调整成了0.95就过了...

后来仔细考虑了一下，这个题的特点在于N很大，M不大

20W个插入，只有2W个查询

如果正常的把参数设为0.75的话，实际效率是接近O(N^(3/2))的

但参数设的比较偏的话，会减少重构次数，查询的复杂度会增加

但实际总复杂度更接近O(M*N(1/2))，所以就能A了

所以通过这个题，我们推荐重构参数设为 M/(N + M) + 0.5