BZOJ 2648: SJY摆棋子(K-D Tree)

Time Limit: 20 Sec  Memory Limit: 128 MB
Submit: 6051  Solved: 2113
[Submit][Status][Discuss]

Description

这天，SJY显得无聊。在家自己玩。在一个棋盘上，有N个黑色棋子。他每次要么放到棋盘上一个黑色棋子，要么放上一个白色棋子，如果是白色棋子，他会找出距离这个白色棋子最近的黑色棋子。此处的距离是 曼哈顿距离 即(|x1-x2|+|y1-y2|) 。现在给出N<=500000个初始棋子。和M<=500000个操作。对于每个白色棋子，输出距离这个白色棋子最近的黑色棋子的距离。同一个格子可能有多个棋子。

Input

第一行两个数 N M

以后M行，每行3个数 t x y

如果t=1 那么放下一个黑色棋子

如果t=2 那么放下一个白色棋子

Output

对于每个T=2 输出一个最小距离

Sample Input

2 3
1 1
2 3
2 1 2
1 3 3
2 4 2

Sample Output

1
2

HINT

kdtree可以过

Source

K-D Tree裸题

洛谷上需要拍扁重构才能过

丧心病狂

#include<cstdio>
#include<algorithm>
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 17, stdin), p1 == p2) ? EOF : *p1++)
using namespace std;
const int MAXN =  * 1e5 + , INF = 1e9 + ;
const double delat = 0.60;
char buf[ << ], *p1 = buf, *p2 = buf;
inline int read() {
    char c = getchar(); int x = , f = ;
    while(c < '' || c > '') {if(c == '-') f = -; c = getchar();}
    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();
    return x * f;
}
int N, M, WD, root, Ans;
inline int abs(int x) {
    return x <  ? -x : x;
}
#define ls(x) T[x].ls
#define rs(x) T[x].rs
struct Point {
    int x[];
    bool operator < (const Point rhs) const {
        return x[WD] < rhs.x[WD];
    }
}p[MAXN];
struct Node {
    int ls, rs, siz, mi[], mx[];
    Point tp;
}T[MAXN];
int rub[MAXN], top, cur;
int NewNode() {
    return top ? rub[top--] : ++cur;//tag
}
void update(int k) {
    T[k].siz = T[ls(k)].siz + T[rs(k)].siz + ;
    for(int i = ; i <= ; i++) {
        T[k].mi[i] = T[k].mx[i] = T[k].tp.x[i];
        if(ls(k)) T[k].mi[i] = min(T[k].mi[i], T[ls(k)].mi[i]), T[k].mx[i] = max(T[k].mx[i], T[ls(k)].mx[i]);
        if(rs(k)) T[k].mi[i] = min(T[k].mi[i], T[rs(k)].mi[i]), T[k].mx[i] = max(T[k].mx[i], T[rs(k)].mx[i]);
    }
}
int Build(int l, int r, int wd) {
    if(l > r) return ;
    int k = NewNode(), mid = l + r >> ;
    WD = wd, nth_element(p + l, p + mid, p + r + );
    T[k].tp = p[mid];
    T[k].ls = Build(l, mid - , wd ^ );
    T[k].rs = Build(mid + , r, wd ^ );
    update(k);
    return k;
}
inline void Apart(int k, int num) {
    if(T[k].ls) Apart(ls(k), num);
    p[num + T[ls(k)].siz + ] = T[k].tp, rub[++top] = k;
    if(T[k].rs) Apart(rs(k), num + T[ls(k)].siz + );
}
inline int check(int &k, int wd) {
    if(T[k].siz * delat < T[ls(k)].siz || T[k].siz * delat < T[rs(k)].siz)
        Apart(k, ), k = Build(, T[k].siz, wd);
}
void Insert(Point a, int &k, int wd) {
    if(k == ) {
        k = NewNode(); T[k].tp = a; update(k); return ;
    }
    if(a.x[wd] < T[k].tp.x[wd]) Insert(a, ls(k), wd ^ );
    else Insert(a, rs(k), wd ^ );
    update(k); check(k, wd);
}
inline int dis(Point a, Point b) {
    return abs(a.x[] - b.x[]) + abs(a.x[] - b.x[]);
}
inline int Manha(Point a, int b) {
    int rt = ;
    for(int i = ; i <= ; i++)
        rt += max(, a.x[i] - T[b].mx[i]) + max(, T[b].mi[i] - a.x[i]);
    return rt;
}
int Query(Point a, int k) {
    Ans = min(Ans, dis(T[k].tp, a));
    int disl = INF, disr = INF;
    if(ls(k)) disl = Manha(a, T[k].ls);
    if(rs(k)) disr = Manha(a, T[k].rs);
    if(disl < disr) {
        if(disl < Ans) Query(a, ls(k));
        if(disr < Ans) Query(a, rs(k));
    }
    else {
        if(disr < Ans) Query(a, rs(k));
        if(disl < Ans) Query(a, ls(k));
    }
}
int main() {
    #ifdef WIN32
    freopen("a.in", "r", stdin);
    #endif
    N = read(); M = read();
    for(int i = ; i <= N; i++)
        p[i].x[] = read(), p[i].x[] = read();
    root = Build(, N, );
    while(M--) {
        int opt = read(), x = read(), y = read();
        if(opt == )
            Insert((Point){x, y}, root, );
        else
            Ans = INF + , Query((Point){x, y}, root), printf("%d\n", Ans);
    }
    return ;
}