您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

BZOJ 2648 SJY擺棋子：KD-Tree 動態維護平面點集最近曼哈頓距離

編輯：關於C++

問題描述

平面上初始有 N (≤ 500,000) 個黑棋子。M (≤ 500,000) 次操作：
1 x y：添加黑棋子；
2 x y：添加白棋子，詢問該白棋子到最近黑棋子的曼哈頓距離。
同一坐標可有多子。輸出每次詢問的答案。

核心數據結構：KD-Tree（K 維樹）

KD-Tree 是平衡二叉空間分割樹，支持：

構建：O(N log N)
單點插入：O(log N) 期望（需定期重構平衡）
最近鄰查詢：O(√N) 期望

本題操作數 50 萬，KD-Tree 是極少數能通過的結構（平衡 BST 無法直接處理曼哈頓距離）。

曼哈頓距離與 KD-Tree 結合

曼哈頓距離 |x₁-x₂| + |y₁-y₂|。KD-Tree 節點維護子樹矩形包圍盒 [minX, maxX] × [minY, maxY]。查詢時，點到矩形的最小曼哈頓距離為：

dx = max(0, max(minX - qx, qx - maxX));
dy = max(0, max(minY - qy, qy - maxY));
minDist = dx + dy;

若 minDist ≥ 當前最佳答案，剪枝該子樹。

關鍵實現細節

構建：遞歸選擇方差較大的維度（或輪流 x/y），用 nth_element 找中位數分割，構建平衡樹。
插入：按構建時的維度分割規則下降到葉子插入。為防止退化，每 K 次插入（如 50 次）觸發一次子樹重構（重新構建該子樹）。
查詢：優先搜索包含查詢點的子樹，利用包圍盒下界剪枝。

複雜度分析

構建：O(N log N)
單次插入：攤仍 O(log N)
單次查詢：期望 O(√N)，最壞 O(N) 但隨機數據極快
總時間：約 1-2 秒內通過 50 萬操作

參考代碼核心結構


struct Node {
    int x[2], ls, rs;
    int mn[2], mx[2];
    bool operator<(const Node& o) const { return x[dim] < o.x[dim]; }
} t[MAXN];

int dim; // 0:x, 1:y

int build(int l, int r, int d) {
    if (l > r) return 0;
    dim = d;
    int mid = (l + r) >> 1;
    nth_element(t + l, t + mid, t + r + 1);
    t[mid].ls = build(l, mid - 1, d ^ 1);
    t[mid].rs = build(mid + 1, r, d ^ 1);
    pushup(mid);
    return mid;
}

void pushup(int u) {
    for (int i = 0; i < 2; i++) {
        t[u].mn[i] = t[u].mx[i] = t[u].x[i];
        if (t[u].ls) {
            t[u].mn[i] = min(t[u].mn[i], t[t[u].ls].mn[i]);
            t[u].mx[i] = max(t[u].mx[i], t[t[u].ls].mx[i]);
        }
        if (t[u].rs) {
            t[u].mn[i] = min(t[u].mn[i], t[t[u].rs].mn[i]);
            t[u].mx[i] = max(t[u].mx[i], t[t[u].rs].mx[i]);
        }
    }
}

int query(int u, int qx, int qy) {
    if (!u) return INF;
    int ans = min(ans, abs(t[u].x[0]-qx) + abs(t[u].x[1]-qy));
    int dl = t[u].ls ? distToRect(qx, qy, t[u].ls) : INF;
    int dr = t[u].rs ? distToRect(qx, qy, t[u].rs) : INF;
    if (dl < dr) {
        if (dl < ans) ans = query(t[u].ls, qx, qy);
        if (dr < ans) ans = query(t[u].rs, qx, qy);
    } else {
        if (dr < ans) ans = query(t[u].rs, qx, qy);
        if (dl < ans) ans = query(t[u].ls, qx, qy);
    }
    return ans;
}