BZOJ 2626 JZPFAR K：KD-Tree 第 K 遠點查詢

問題描述

平面 n (≤100,000) 個點，q (≤100,000) 次詢問：給定點 p 和整數 k，求距離 p 第 k 遠的點的編號。距離為歐氏距離平方。

KD-Tree + 小頂堆

• 構建 KD-Tree（同 BZOJ 1941，但用歐氏距離平方）
• 每個節點維護子樹邊界框，計算查詢點到邊界框的 最大可能距離（四個角點取最大）
• 查詢時維護大小為 k 的小頂堆，存儲目前找到的 k 個最遠點
• 剪枝：子樹最大可能距離 ≤ 堆頂（當前第 k 遠）則放棄

距離函數

long long dist2(Point a, Point b) {
    long long dx = a.x - b.x, dy = a.y - b.y;
    return dx*dx + dy*dy;
}
long long maxDist2(KDNode* node, Point p) {
    long long d = 0;
    d = max(d, dist2(p, {node->x0, node->y0}));
    d = max(d, dist2(p, {node->x1, node->y0}));
    d = max(d, dist2(p, {node->x1, node->y1}));
    d = max(d, dist2(p, {node->x0, node->y1}));
    return d;
}

查詢遞歸

void query(KDNode* node, Point p, int k, priority_queue& pq) {
    if (!node) return;
    long long d = dist2(p, node->pt);
    Item cur(d, node->pt.id);
    if (cur < pq.top()) { pq.push(cur); pq.pop(); } // 小頂堆，保持 k 最大
    long long dl = node->ch[0] ? maxDist2(node->ch[0], p) : -1;
    long long dr = node->ch[1] ? maxDist2(node->ch[1], p) : -1;
    if (dl > dr) {
        if (dl >= pq.top().dist) query(node->ch[0], p, k, pq);
        if (dr >= pq.top().dist) query(node->ch[1], p, k, pq);
    } else {
        if (dr >= pq.top().dist) query(node->ch[1], p, k, pq);
        if (dl >= pq.top().dist) query(node->ch[0], p, k, pq);
    }
}

關鍵點

1. 小頂堆維護「前 k 大」，堆頂即為當前第 k 遠距離，作為剪枝閾值
2. 優先搜索最大可能距離更大的子樹，盡快提高閾值
3. 初始堆填入 k 個距離 -1 的佔位符
4. 距離相同時按編號小優先（題目要求），`Item` 比較函數處理

複雜度

• 構建：O(n log n)
• 單次查詢：平均 O(√n + k log k)，最壞 O(n)
• 總計：可通過 10 萬點、10 萬查詢

此題是 KD-Tree 解決「第 k 近/遠鄰」的經典應用，堆 + 剪枝 結合優先搜索是核心技巧。