【bzoj2648】SJY摆棋子（kdtree）

题意：

二维平面上有若干个点。

现在要维护一种数据结构，支持插入一个点以及询问其余点到某个点的最小曼哈顿距离。

思路：

这是个\(kdtree\)模板题。

\(kdtree\)是一种可以高效处理\(k\)维空间信息的结构。一般我们遇到的是\(2\)维空间或者\(3\)维空间。

一般用来解决的问题为：空间最近点对、空间第\(k\)远点对、矩阵查询等问题，这些问题离线可以离线\(cdq\)解决，但是用\(kdtree\)的话可以在线处理这些问题。

一般认为一次操作期望复杂度是\(\sqrt{n}\)的，但最坏情况下复杂度为\(O(n)\)。所以我们其实可以将它看作一种玄学且比较优美的暴力~一般我们都直接定义全局变量然后大力减枝。

开局建颗树，减枝刷题数！

回到这个题，查询的话\(ans\)注意是全局变量。另外还定义了一个估价函数，含义是到达那个矩形内部的最好情况，显然这个最好情况如果都大于目前的\(ans\)，我们可以不用搜索该子树。

如果类似于一个圆就可能被卡到\(O(n^2)\)

细节见代码：

/*

 * Author:  heyuhhh

 * Created Time:  2019/11/22 14:12:30

 */

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <vector>

#include <cmath>

#include <set>

#include <map>

#include <iomanip>

#define MP make_pair

#define fi first

#define se second

#define sz(x) (int)(x).size()

#define all(x) (x).begin(), (x).end()

#define INF 0x3f3f3f3f

#define Local

#ifdef Local

  #define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)

  void err() { std::cout << '\n'; }

  template<typename T, typename...Args>

  void err(T a, Args...args) { std::cout << a << ' '; err(args...); }

#else

  #define dbg(...)

#endif

void pt() {std::cout << '\n'; }

template<typename T, typename...Args>

void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }

using namespace std;

typedef long long ll;

typedef pair<int, int> pii;

//head

const int N = 1e6 + 5;

inline int read()

{

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

int n, m;

int D;

const int dim = 2;

struct Point {

    int d[2], mn[2], mx[2], l, r;

    int& operator [] (int x) {return d[x];}

    Point(int x = 0, int y = 0) {

        l = r = 0;

        d[0] = x; d[1] = y;

    }

}p[N >> 1];

bool operator < (Point A, Point B) {

    return A[D] < B[D];

}

struct kdtree {

    int rt, ans; //注意ans定义为全局变量

    Point tree[N], T;

    void upd(int o) {

        Point ls = tree[tree[o].l], rs = tree[tree[o].r];

        for(int i = 0; i < dim; i++) {

            if(tree[o].l) {

                tree[o].mn[i] = min(tree[o].mn[i], ls.mn[i]);

                tree[o].mx[i] = max(tree[o].mx[i], ls.mx[i]);

            }

            if(tree[o].r) {

                tree[o].mn[i] = min(tree[o].mn[i], rs.mn[i]);

                tree[o].mx[i] = max(tree[o].mx[i], rs.mx[i]);

            }

        }

    }

    int build(int l, int r, int now) {

        D = now;

        int mid = (l + r) >> 1;

        nth_element(p + l, p + mid, p + r + 1);

        tree[mid] = p[mid];

        for(int i = 0; i < dim; i++) {

            tree[mid].mn[i] = tree[mid].mx[i] = tree[mid][i];

        }

        if(l < mid) tree[mid].l = build(l, mid - 1, now ^ 1);

        if(r > mid) tree[mid].r = build(mid + 1, r, now ^ 1);

        upd(mid);

        return mid;

    }

    void insert(int o, int now) {

        D = now;

        if(T[D] < tree[o][D]) {

            if(tree[o].l) insert(tree[o].l, now ^ 1);

            else {

                tree[o].l = ++n;

                tree[n] = T;

                for(int i = 0; i < dim; i++) {

                    tree[n].mx[i] = tree[n].mn[i] = T[i];

                }

            }

        } else {

            if(tree[o].r) insert(tree[o].r, now ^ 1);

            else {

                tree[o].r = ++n;

                tree[n] = T;

                for(int i = 0; i < dim; i++) {

                    tree[n].mx[i] = tree[n].mn[i] = T[i];

                }

            }

        }

        upd(o);

    }

    int dis(Point A, Point B) {

        int res = 0;

        for(int i = 0; i < dim; i++) {

            res += abs(A[i] - B[i]);

        }

        return res;

    }

    int get(Point A, Point B) {//估价函数

        int res = 0;

        for(int i = 0; i < dim; i++) {

            res += max(0, A[i] - B.mx[i]) + max(0, B.mn[i] - A[i]);

        }

        return res;

    }

    void query(int o) {

        ans = min(ans, dis(tree[o], T));

        int l = INF, r = INF;

        if(tree[o].l) l = get(T, tree[tree[o].l]);

        if(tree[o].r) r = get(T, tree[tree[o].r]);

        if(l < r) {

            if(l < ans) query(tree[o].l);

            if(r < ans) query(tree[o].r);

        } else {

            if(r < ans) query(tree[o].r);

            if(l < ans) query(tree[o].l);

        }

    }

}kd;

void run(){

    n = read(), m = read();

    for(int i = 1; i <= n; i++) {

        int x = read(), y = read();

        p[i] = Point(x, y);

    }

    kd.rt = kd.build(1, n, 0);

    while(m--) {

        int t = read(), x = read(), y = read();

        kd.T = Point(x, y);

        if(t == 1) {

            kd.insert(kd.rt, 0);

        } else {

            kd.ans = INF;

            kd.query(kd.rt);

            printf("%d\n", kd.ans);

        }

    }

}

int main() {

    run();

    return 0;

}

巴特西

【bzoj2648】SJY摆棋子（kdtree）

最新文章

热门文章