[BZOJ2716/2648][Violet 3]天使玩偶/SJY摆棋子[KDtree]

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]的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。