KDtree干這個復雜度是不對的，重構不一定有作用

解釋一下的話，因為復雜度是跟size相關的，所以重構作用不大，KDtree在查詢最近點對中的作用僅僅是剪枝，可以構造數據使得他遍歷O(n)個節點

hack kdtree

（上面這個是按照洛谷數據范圍 n,m 3e5造的

int n, m, x, y, now, ans, op, cnt, d[2]; struct Node {int Min[2], Max[2], d[2];Node *ls, *rs;Node (const pii &a, Node *b) {Min[0] = Max[0] = d[0] = a.fi;Max[1] = Min[1] = d[1] = a.se;ls = rs = b;}Node () {}inline void pushup() {lop0(i, 2) Min[i] = min(d[i], min(ls->Min[i], rs->Min[i])), Max[i] = max(d[i], max(ls->Max[i], rs->Max[i]));}inline bool operator < (const Node &rhs) const {return d[now] < rhs.d[now];} } S[1300005], *null = S, *root, *root1; inline void init() {null->Min[0] = null->Min[1] = 1e7, null->Max[0] = null->Max[1] = -1e7;//1e9???èˉ dis??????intnull->ls = null->rs = null;root1 = root = null; } inline Node *build(int l, int r) {if (l > r) return null;nth_element(S+l, S+mid, S+r+1);Node *cur = &S[mid];now ^= 1;cur->ls = build(l, mid-1), cur->rs = build(mid+1, r);return cur->pushup(), cur; } inline void insert(Node *&cur, int *d, bool now) {if (cur == null) {cur = &(S[++cnt] = Node(mp(d[0],d[1]), null));return ;}insert(d[now] >= cur->d[now] ? cur->rs : cur->ls, d, !now);cur->pushup(); }inline int dis(Node *cur, const pii &a) {return max(0, a.se - cur->Max[1]) + max(0, a.fi - cur->Max[0]) + max(0, cur->Min[0] - a.fi) + max(0, cur->Min[1] - a.se); } inline void query(Node *cur, const pii &a) {chmin(ans, abs(cur->d[0] - a.fi) + abs(cur->d[1] - a.se));int disl = dis(cur->ls, a), disr = dis(cur->rs, a);if (disl < disr) {if (disl < ans) query(cur->ls, a);if (disr < ans) query(cur->rs, a);}else {if (disr < ans) query(cur->rs, a);if (disl < ans) query(cur->ls, a);} }int main() {init();in, cnt, m;lop1(i, cnt) {in, x, y;S[i] = Node(mp(x, y), null);}root = build(1, cnt);while (m--) { in, op, x, y;if (op == 1) {d[0] = x, d[1] = y;insert(root, d, 0);}else {ans = inft;query(root, mp(x, y));out, ans, '\n';}} return 0; }

轉載于:https://www.cnblogs.com/storz/p/10264134.html

總結

以上是生活随笔為你收集整理的[BZOJ2716/2648][Violet 3]天使玩偶/SJY摆棋子[KDtree]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。