BZOJ 2648 k-d tree

题

给一个二维平面。两种操作，1）加一个点，2）对一个坐标查一个曼哈顿距离最近的点的距离。

解

不会做。
但是我会抄代码啊233333
其实很早前看了一遍k-d tree的思想，照着黄学长代码打了一遍感觉很多地方都挺好懂的。
当然赛场上写不出来233

比较不理解的就是query里的分情况递归先后顺序有什么区别。
迟早得重新学（x。

话说最近真的好奇怪啊……
一发呆胡思乱想就半个钟过了……一天下来这是第几次了……我到底怎么才能恢复呢……

码（47708 kb 12988 ms）

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
const int maxn = 500005, maxm = 1000005, INF = 0x3f3f3f3f;
int n, m, root, D;
struct Point
{
    int d[2], _min[2], _max[2], l, r;
    int& operator[](int x){return d[x];}
    Point(int x = 0, int y = 0){l = 0, r = 0; d[0] = x, d[1] = y;}
    bool operator<(const Point& rhs) const {return d[D] < rhs.d[D];}
} p[maxn];
inline int dis(Point a, Point b){return abs(a[0] - b[0]) + abs(a[1] - b[1]);}
struct kdtree
{
    int ans;
    Point t[maxm], T;
    void update(int k)
    {
        Point l = t[t[k].l], r = t[t[k].r];
        for(int i = 0; i < 2; i++)
        {
            if(t[k].l) t[k]._min[i] = min(t[k]._min[i], l._min[i]), t[k]._max[i] = max(t[k]._max[i], l._max[i]);
            if(t[k].r) t[k]._min[i] = min(t[k]._min[i], r._min[i]), t[k]._max[i] = max(t[k]._max[i], r._max[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);
        t[mid] = p[mid];
        for(int i = 0; i < 2; i++)
            t[mid]._min[i] = t[mid]._max[i] = t[mid][i];
        if(l < mid) t[mid].l = build(l, mid - 1, now ^ 1);
        if(mid < r) t[mid].r = build(mid + 1, r, now ^ 1);
        update(mid);
        return mid;
    }
    int get(int k, Point p)
    {
        int tmp = 0;
        for(int i = 0; i < 2; i++) tmp += max(0, t[k]._min[i] - p[i]);
        for(int i = 0; i < 2; i++) tmp += max(0, p[i] - t[k]._max[i]);
        return tmp;
    }
    void insert(int k, int now)
    {
        if(T[now] >= t[k][now])
        {
            if(t[k].r) insert(t[k].r, now ^ 1);
            else
            {
                t[k].r = ++n; t[n] = T;
                for(int i = 0; i < 2; i++) t[n]._min[i] = t[n]._max[i] = t[n][i];
            }
        }
        else
        {
            if(t[k].l) insert(t[k].l, now ^ 1);
            else
            {
                t[k].l = ++n; t[n] = T;
                for(int i = 0; i < 2; i++) t[n]._min[i] = t[n]._max[i] = t[n][i];
            }
        }
        update(k);
    }
    void query(int k, int now)
    {
        int d, dl = INF, dr = INF;
        d = dis(t[k], T);
        ans = min(ans, d);
        if(t[k].l) dl = get(t[k].l, T);
        if(t[k].r) dr = get(t[k].r, T);
        if(dl < dr)
        {
            if(dl < ans) query(t[k].l, now ^ 1);
            if(dr < ans) query(t[k].r, now ^ 1);
        }
        else
        {
            if(dr < ans) query(t[k].r, now ^ 1);
            if(dl < ans) query(t[k].l, now ^ 1);
        }
    }
    int query(Point p)
    {
        ans = INF; T = p; query(root, 0);
        return ans;
    }
    void insert(Point p)
    {
        T = p; insert(root, 0);
    }
} kd;
int main()
{
    read(n, m);
    for(int i = 1; i <= n; i++) read(p[i][0], p[i][1]);
    root = kd.build(1, n, 0);
    while(m--)
    {
        int op, x, y; read(op, x, y);
        if(op == 1) kd.insert(Point(x, y));
        else printf("%d\n", kd.query(Point(x, y)));
    }
    return 0;
}