注意，此 Trick 的时间复杂度是错的，但是貌似目前没人能卡满。
能够解决的问题
- \(O(n \sqrt n)\) 可过。
- 维护二维平面。
- 每次求到一个点的 \(k\) 近或 \(k\) 远点。
- \(k\) 很小（\(20\) 左右）
思路
二维空间想到 KDTree（TreeKevin Durant Tree）。
众所周知，动态维护 \(k\) 近或 \(k\) 远点只需要一个 \(k\) 个点的堆即可，那么我们就有了一个剪枝：当前节点维护的区间到询问点的理论极值（写个估价函数就行）都比不上当前 \(k\) 大/小值，就返回。
结束了，就是这么简单。
例题与代码
P2093 [国家集训队] JZPFAR - 洛谷
#include <bits/stdc++.h>
using namespace std;namespace gxk {void main() ;
}
int main() {ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);gxk::main();return 0;
}// ---#define int long long
namespace gxk {constexpr int maxn = 100010;struct point {int x[2];} p;int n, m, x, b[maxn];struct value {int dis, idx;bool operator < (const value o) const {return dis > o.dis || (dis == o.dis && idx < o.idx);}} ;priority_queue <value> q;struct Kevin_DurantNode {point x, l, r;int ls, rs, idx;} nodes[maxn];int cnt;struct Kevin_DurantTree {void pushup(int u) {for (int k = 0; k < 2; k++) {nodes[u].l.x[k] = nodes[u].r.x[k] = nodes[u].x.x[k];if (nodes[u].ls) {nodes[u].l.x[k] = min(nodes[u].l.x[k], nodes[nodes[u].ls].l.x[k]);nodes[u].r.x[k] = max(nodes[u].r.x[k], nodes[nodes[u].ls].r.x[k]);}if (nodes[u].rs) {nodes[u].l.x[k] = min(nodes[u].l.x[k], nodes[nodes[u].rs].l.x[k]);nodes[u].r.x[k] = max(nodes[u].r.x[k], nodes[nodes[u].rs].r.x[k]);}}return ;}void build(int &u, int l, int r, int k) {int midd = ((l + r) >> 1);nth_element(b + l, b + midd, b + r + 1, [k](int a, int b){return nodes[a].x.x[k] < nodes[b].x.x[k];});u = b[midd];
// cout << nodes[u].x.x[0] << ' ' << nodes[u].x.x[1] << '\n';if (l < midd) build(nodes[u].ls, l, midd - 1, k ^ 1);if (r > midd) build(nodes[u].rs, midd + 1, r, k ^ 1);pushup(u);return ;}int dis(int x, int y) {return (x - p.x[0]) * (x - p.x[0]) + (y - p.x[1]) * (y - p.x[1]);}int evaluate(int u) {return max({dis(nodes[u].l.x[0], nodes[u].l.x[1]), dis(nodes[u].l.x[0], nodes[u].r.x[1]), dis(nodes[u].r.x[0], nodes[u].l.x[1]), dis(nodes[u].r.x[0], nodes[u].r.x[1])});}void query(int u) {value now = {evaluate(u), nodes[u].idx};if (!(now < q.top())) return ;now = {dis(nodes[u].x.x[0], nodes[u].x.x[1]), nodes[u].idx};if (now < q.top()) q.pop(), q.push(now);if (nodes[u].ls && nodes[u].rs) {value vl = {evaluate(nodes[u].ls), nodes[nodes[u].ls].idx}, vr = {evaluate(nodes[u].rs), nodes[nodes[u].rs].idx};if (vl < vr) {query(nodes[u].ls);query(nodes[u].rs);} else {query(nodes[u].rs);query(nodes[u].ls);}} else if (nodes[u].ls) {query(nodes[u].ls);} else if (nodes[u].rs) {query(nodes[u].rs);}return ;}} kdt;int root;void main() {cin >> n;cnt = n;for (int i = 1; i <= n; i++) {cin >> nodes[i].x.x[0] >> nodes[i].x.x[1];nodes[i].idx = i;b[i] = i;}kdt.build(root, 1, n, 0);cin >> m;while (m--) {cin >> p.x[0] >> p.x[1] >> x;while (!q.empty()) q.pop();while (x--) {q.push({-1, 0});}kdt.query(root);cout << q.top().idx << '\n';}return ;}
}