解题思路

2016 ICPC 青岛 的一道金牌题，是 K-D Tree 的典型应用。

我们可以按 x, y, c 建立三维 K-D Tree，查询的时候如果 c 过大，则直接把当前搜到的 dis 设置为 INF，其他操作和普通 K-D Tree 基本一致。

另外应注意，如果直接使用输入时的数组 Build，可能会被 nth_element() 打乱顺序，因此更新答案时需要记录原数组中的下标信息。

参考代码

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;

const long long INF = 1e18;
const int MAXN = 200001;
const int MAXK = 3;
const int K = 3;

struct node {
    long long d[MAXK];
    int id;
    long long min[MAXK], max[MAXK];
    int l, r;
} t[MAXN];

int D, root;
long long p[MAXK];
long long bak[MAXN][MAXK]; // bak 用于备份初始数据，Build 后数组会乱序！
pair<long long, int> ans;

void Print() {
    for(int i=0; i<=3; ++i) {
            for(int j=0; j<K; ++j) {
                printf("%lld ", t[i].d[j]);
            }
            printf(" %d\n", t[i].id);
        }
        printf("\n");
}

bool cmp(node a, node b) {
    return a.d[D] < b.d[D];
}

void Update(int x) {
    int l = t[x].l, r = t[x].r;
    for(int i=0; i<K; ++i) {
        t[x].min[i] = min(t[x].min[i], min(t[l].min[i], t[r].min[i]));
        t[x].max[i] = max(t[x].max[i], max(t[l].max[i], t[r].max[i]));
    }
}

int Build(int l, int r, int d) {
    D = d;
    int mid = (l+r) >> 1;
    nth_element(t+l, t+mid, t+r+1, cmp);
    if(mid != l) t[mid].l = Build(l, mid-1, (d+1)%K);
    else t[mid].l = 0;
    if(mid != r) t[mid].r = Build(mid+1, r, (d+1)%K);
    else t[mid].r = 0;

    Update(mid);

    return mid;
}

inline long long Pow(long long x) {
    return x * x;
}

long long Dis(int x) {
    long long ret = 0;
    for(int i=0; i<K-1; ++i) {
        ret += Pow(t[x].d[i]-p[i]);
    }

    return ret;
}

long long GetDis(int x) {
    if(p[2] < t[x].min[2]) return INF;
    long long ret = 0;
    for(int i=0; i<K-1; ++i) {
        if(p[i] < t[x].min[i])
            ret += Pow(t[x].min[i]-p[i]);
        if(p[i] > t[x].max[i])
            ret += Pow(p[i]-t[x].max[i]);
    }

    return ret;
}

void Query(int x) {
    if(!x) return;
    pair<long long, int> d0 = make_pair(INF, t[x].id);
    if(t[x].d[2] <= p[2]) d0.first = Dis(x);
    pair<long long, int> dl = make_pair(GetDis(t[x].l), t[t[x].l].id);
    pair<long long, int> dr = make_pair(GetDis(t[x].r), t[t[x].r].id);
    if(d0 < ans) ans = d0;
    if(dl < dr) {
        if(dl < ans) Query(t[x].l);
        if(dr < ans) Query(t[x].r);
    }
    else {
        if(dr < ans) Query(t[x].r);
        if(dl < ans) Query(t[x].l);
    }
}

int main(int argc, char const *argv[]) {
    int T, n, m;
    scanf("%d", &T);
    while(T--) {
        scanf("%d %d", &n, &m);
        for(int i=0; i<K; ++i) {
            t[0].min[i] = INF;
            t[0].max[i] = -INF;
        }
        for(int i=1; i<=n; ++i) {
            for(int j=0; j<K; ++j) {
                scanf("%lld", &t[i].d[j]);
                t[i].min[j] = t[i].max[j] = t[i].d[j];
                bak[i][j] = t[i].d[j];
            }
            t[i].id = i;
        }
        root = Build(1, n, 0);
        while(m--) {
            for(int i=0; i<K; ++i) {
                scanf("%d", &p[i]);
            }
            ans.first = INF;
            ans.second = 0;
            Query(root);
            printf("%lld %lld %lld\n", bak[ans.second][0], bak[ans.second][1], bak[ans.second][2]);
        }
    }
    
    return 0;
}