K-D Tree

bool o;//当前维度
struct point 
{
    int p[2];
    friend bool operator <(point A, point B) { return A.p[o] < B.p[o]; }
    friend bool operator !=(point A, point B) { return A.p[0] != B.p[0] | A.p[1] != B.p[1]; }
}; point a[Z];
inline int calc(point x, point y) { return abs(x.p[0] - y.p[0]) + abs(x.p[1] - y.p[1]); }
struct KDtree
{
    int l, r;
    point pt;
    int max[2], min[2];//最大与最小的横纵坐标
    #define lk kd[rt].l
    #define rk kd[rt].r
}; KDtree kd[Z];
int root, inf = 2e9;
inline void pushup(int rt)
{
    for (re i = 0; i <= 1; i++)
    {
        if (lk) kd[rt].max[i] = max(kd[rt].max[i], kd[lk].max[i]), kd[rt].min[i] = min(kd[rt].min[i], kd[lk].min[i]);
        if (rk) kd[rt].max[i] = max(kd[rt].max[i], kd[rk].max[i]), kd[rt].min[i] = min(kd[rt].min[i], kd[rk].min[i]);
    }
}
int build(int l, int r, bool op)
{
    o = op;//自定义排序方式（表示维度）
    int rt = l + r >> 1;
    nth_element(a + l, a + rt, a + r + 1);//定位中位数
    kd[rt].pt = a[rt];
    for (re i = 0; i <= 1; i++) kd[rt].max[i] = kd[rt].min[i] = a[rt].p[i];
    if (l < rt) lk = build(l, rt - 1, op ^ 1);
    if (r > rt) rk = build(rt + 1, r, op ^ 1);
    pushup(rt); return rt;
}
int Max, Min;
inline int estimate_max(int rt, point x)//估价函数
{
    int sum = 0;
    for (re i = 0; i <= 1; i++)//找到理论极限距离最大的点对（已扩展的最大平面的顶点）
        sum += max(abs(kd[rt].max[i] - x.p[i]), abs(kd[rt].min[i] - x.p[i]));
    return sum;
}
inline int estimate_min(int rt, point x)
{
    int sum = 0;
    for (re i = 0; i <= 1; i++)//如果处于max和min的两侧，直接取最近；如果处于中间，则不知道还有没有其他的点，无法预估
        sum += max(x.p[i] - kd[rt].max[i], 0) + max(kd[rt].min[i] - x.p[i], 0);
    return sum;
}
void query_max(int rt, point x)
{
    Max = max(Max, calc(kd[rt].pt, x));
    int el = 0, er = 0;
    if (lk) el = estimate_max(lk, x);
    if (rk) er = estimate_max(rk, x);
    if (el > er)//先跑最有可能达到最大值的
    {
        if (Max < el) query_max(lk, x);
        if (Max < er) query_max(rk, x);
    }
    else
    {
        if (Max < er) query_max(rk, x);
        if (Max < el) query_max(lk, x);
    }
}
void query_min(int rt, point x)
{
    if (kd[rt].pt != x) Min = min(Min, calc(kd[rt].pt, x));
    int el = inf, er = inf;
    if (lk) el = estimate_min(lk, x);
    if (rk) er = estimate_min(rk, x);
    if (el < er)//先跑最有可能达到最小值的
    {
        if (Min > el) query_min(lk, x);
        if (Min > er) query_min(rk, x);
    }
    else
    {
        if (Min > er) query_min(rk, x);
        if (Min > el) query_min(lk, x);
    }
}
inline int ask(point x)
{
    Max = 0, Min = inf;
    query_max(root, x), query_min(root, x);
    return Max - Min;
}