BZOJ 2648 SJY 擺棋子 —— K-D Tree 動態最近鄰查詢（插入 + 查詢）

BZOJ 2648：平面上動態維护黑棋子集合，支持兩種操作（N, M ≤ 5×10⁵）：

1. 插入黑棋 (x, y)
2. 查詢白棋 (x, y) 到最近黑棋的曼哈頓距離 |x1-x2| + |y1-y2|

經典K-D Tree動態最近鄰搜索模板題。

一、K-D Tree 核心結構

struct Node {
    int d[2];      // 點座標
    int mn[2], mx[2]; // 子樹包絡盒
    int l, r;      // 左右孩子索引
} t[maxn];

二、構建：靜態構建 + 動態插入

• 初始 N 個點用 nth_element 遞歸構建平衡 K-D Tree，O(N log N)。
• 後續插入沿樹比較對應維度 D ^= 1 走向葉子，O(log N) 期望（退化時需重建，本題數據隨機可不重建）。

三、最近鄰查詢剪枝策略

對當前節點 k，計算查詢點到左右子樹包絡盒的最小可能曼哈頓距離 dl, dr：

int getMinDist(int k, const Node& q) {
    int dx = 0, dy = 0;
    if (q.d[0] < t[k].mn[0]) dx = t[k].mn[0] - q.d[0];
    else if (q.d[0] > t[k].mx[0]) dx = q.d[0] - t[k].mx[0];
    if (q.d[1] < t[k].mn[1]) dy = t[k].mn[1] - q.d[1];
    else if (q.d[1] > t[k].mx[1]) dy = q.d[1] - t[k].mx[1];
    return dx + dy;
}

優先遞歸 min(dl, dr) 那側；若當前最佳答案 ans ≤ min(dl, dr) 則剪枝另一側。

四、關鍵代碼片段

// 構建
int build(int l, int r, int dim) {
    D = dim;
    int mid = (l+r)>>1;
    nth_element(p+l, p+mid, p+r+1);
    t[mid] = p[mid];
    t[mid].mn[0]=t[mid].mx[0]=t[mid].d[0];
    t[mid].mn[1]=t[mid].mx[1]=t[mid].d[1];
    if (l < mid) t[mid].l = build(l, mid-1, dim^1);
    if (mid < r) t[mid].r = build(mid+1, r, dim^1);
    pushup(mid);
    return mid;
}

// 插入
void insert(int k, int dim) {
    if (tmp.d[dim] >= t[k].d[dim]) {
        if (t[k].r) insert(t[k].r, dim^1);
        else { t[k].r = ++tot; t[tot] = tmp; initNode(tot); }
    } else {
        if (t[k].l) insert(t[k].l, dim^1);
        else { t[k].l = ++tot; t[tot] = tmp; initNode(tot); }
    }
    pushup(k);
}

// 查詢
void query(int k, int dim) {
    ans = min(ans, manhattan(t[k], tmp));
    int dl = t[k].l ? getMinDist(t[k].l, tmp) : INF;
    int dr = t[k].r ? getMinDist(t[k].r, tmp) : INF;
    if (dl < dr) {
        if (dl < ans) query(t[k].l, dim^1);
        if (dr < ans) query(t[k].r, dim^1);
    } else {
        if (dr < ans) query(t[k].r, dim^1);
        if (dl < ans) query(t[k].l, dim^1);
    }
}

五、複雜度與工程優化

• 構建 O(N log N)，單次插入/查詢期望 O(log N)，最差 O(√N)。
• 用 static 數組避免 new/delete 開銷。
• 快速輸入 read()，manhattan 用內聯函數。
• 若退化嚴重可加入「重建閾值」（子樹大小 > α·父樹大小時重建），本題測試數據通常不需。

六、樣例驗證

Input:
2 3
1 1
2 3
2 1 2
1 3 3
2 4 2

Output:
1
2