问题背景与复杂度分析

在三维空间中动态维护点集，并支持两种操作：添加新点和查询距离给定点曼哈顿距离最近的点。该问题是经典二维问题（如"天使玩偶"）的三维扩展。在二维情况下，通常采用 CDQ 分治算法解决，时间复杂度为 $O(n \log^2 n)$。然而，将其直接扩展到三维时，若使用 CDQ 分治嵌套树状数组，时间复杂度将上升至 $O(n \log^3 n)$，在严格的时间限制下极易超时。

相比之下，三维树状数组（Fenwick Tree）在理论上具有更小的常数因子。尽管三维树状数组的空间复杂度较高，但通过一维数组扁平化映射以及精细的常数优化，可以在实际运行中取得更好的性能。

核心算法思路：曼哈顿距离去绝对值

曼哈顿距离的定义为 $|x_2 - x_1| + |y_2 - y_1| + |z_2 - z_1|$。绝对值的存在使得直接进行数据结构维护变得困难。为了消除绝对值，我们可以根据查询点 $(x_2, y_2, z_2)$ 与数据点 $(x_1, y_1, z_1)$ 的相对位置关系，将空间划分为 8 个象限。

以 $x_1 \le x_2, y_1 \le y_2, z_1 \le z_2$ 这一象限为例，距离公式可化简为：

$$(x_2 - x_1) + (y_2 - y_1) + (z_2 - z_1) = (x_2 + y_2 + z_2) - (x_1 + y_1 + z_1)$$

对于固定的查询点，$(x_2 + y_2 + z_2)$ 是常数。因此，问题转化为在该象限内寻找 $(x_1 + y_1 + z_1)$ 的最大值。这可以通过三维树状数组或 CDQ 分治来维护前缀最大值。对于其他 7 个象限，只需对坐标轴进行相应的翻转（如将 $x$ 替换为 $X_{max} - x$），即可转化为相同的形式进行处理。

实现方案一：三维树状数组（BIT）

为了避免多维数组带来的内存碎片和访问开销，我们使用一维数组来模拟三维树状数组。通过哈希函数将三维坐标 $(x, y, z)$ 映射为一维索引。同时，将 8 个象限的处理逻辑封装在循环中，大幅减少代码冗余。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = 0x3f3f3f3f;

class Fenwick3D {
private:
    int dimX, dimY, dimZ;
    vector<int> tree;

    inline int flatten(int x, int y, int z) const {
        return (x * dimY + y) * dimZ + z;
    }

public:
    Fenwick3D(int x, int y, int z) : dimX(x), dimY(y), dimZ(z) {
        tree.assign((x + 1) * (y + 1) * (z + 1), 0);
    }

    void update(int x, int y, int z, int val) {
        for (int i = x; i <= dimX; i += i & -i) {
            for (int j = y; j <= dimY; j += j & -j) {
                for (int k = z; k <= dimZ; k += k & -k) {
                    int idx = flatten(i, j, k);
                    tree[idx] = max(tree[idx], val);
                }
            }
        }
    }

    int query(int x, int y, int z) {
        int maxVal = 0;
        for (int i = x; i > 0; i -= i & -i) {
            for (int j = y; j > 0; j -= j & -j) {
                for (int k = z; k > 0; k -= k & -k) {
                    maxVal = max(maxVal, tree[flatten(i, j, k)]);
                }
            }
        }
        return maxVal == 0 ? INF : maxVal;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int dimX, dimY, dimZ, q;
    if (!(cin >> dimX >> dimY >> dimZ >> q)) return 0;

    dimX++; dimY++; dimZ++;
    vector<Fenwick3D> bits;
    bits.reserve(8);
    for (int i = 0; i < 8; ++i) {
        bits.emplace_back(dimX, dimY, dimZ);
    }

    int dx[] = {1, 1, 1, 1, -1, -1, -1, -1};
    int dy[] = {1, 1, -1, -1, 1, 1, -1, -1};
    int dz[] = {1, -1, 1, -1, 1, -1, 1, -1};

    auto getCoord = [&](int x, int y, int z, int dir) {
        int nx = (dx[dir] == 1) ? x : (dimX - x);
        int ny = (dy[dir] == 1) ? y : (dimY - y);
        int nz = (dz[dir] == 1) ? z : (dimZ - z);
        return make_tuple(nx, ny, nz);
    };

    while (q--) {
        int op, x, y, z;
        cin >> op >> x >> y >> z;
        if (op == 1) {
            for (int i = 0; i < 8; ++i) {
                auto [nx, ny, nz] = getCoord(x, y, z, i);
                bits[i].update(nx, ny, nz, nx + ny + nz);
            }
        } else {
            int ans = INF;
            for (int i = 0; i < 8; ++i) {
                auto [nx, ny, nz] = getCoord(x, y, z, i);
                int maxVal = bits[i].query(nx, ny, nz);
                if (maxVal != INF) {
                    ans = min(ans, (nx + ny + nz) - maxVal);
                }
            }
            cout << ans << "\n";
        }
    }
    return 0;
}

实现方案二：CDQ 分治嵌套树状数组

当空间限制极为严格，无法开辟三维树状数组时，CDQ 分治是更优的选择。我们将问题降维：第一维通过 CDQ 分治按时间或 $x$ 坐标排序，第二维在分治合并时通过归并排序处理 $y$ 坐标，第三维则使用一维树状数组维护 $z$ 坐标的前缀最大值。

为了处理 8 个象限，我们在主函数中通过循环对坐标进行翻转，并多次执行 CDQ 分治。这种写法虽然常数较大，但空间复杂度仅为 $O(n)$。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = 0x3f3f3f3f;

struct Operation {
    int id, x, y, z, type, val;
    bool isActive;
};

int dimZ;
vector<int> bitTree;

inline void updateBIT(int idx, int val) {
    for (; idx <= dimZ; idx += idx & -idx)
        bitTree[idx] = max(bitTree[idx], val);
}

inline int queryBIT(int idx) {
    int res = -INF;
    for (; idx > 0; idx -= idx & -idx)
        res = max(res, bitTree[idx]);
    return res;
}

inline void clearBIT(int idx) {
    for (; idx <= dimZ; idx += idx & -idx)
        bitTree[idx] = 0;
}

vector<Operation> tempOps;

void cdqY(int left, int right, vector<Operation>& ops, vector<int>& answers) {
    if (left == right) return;
    int mid = (left + right) / 2;
    cdqY(left, mid, ops, answers);
    cdqY(mid + 1, right, ops, answers);

    int i = left, j = mid + 1, k = left;
    while (j <= right) {
        while (i <= mid && ops[i].y <= ops[j].y) {
            if (ops[i].type == 1 && ops[i].isActive) {
                updateBIT(ops[i].z, ops[i].val);
            }
            tempOps[k++] = ops[i++];
        }
        if (ops[j].type == 2 && !ops[j].isActive) {
            int maxVal = queryBIT(ops[j].z);
            if (maxVal != -INF) {
                answers[ops[j].id] = min(answers[ops[j].id], ops[j].val - maxVal);
            }
        }
        tempOps[k++] = ops[j++];
    }
    
    for (int p = left; p < i; ++p) {
        if (ops[p].type == 1 && ops[p].isActive) clearBIT(ops[p].z);
    }
    
    while (i <= mid) tempOps[k++] = ops[i++];
    for (int p = left; p <= right; ++p) ops[p] = tempOps[p];
}

void cdqX(int left, int right, vector<Operation>& ops, vector<int>& answers) {
    if (left == right) return;
    int mid = (left + right) / 2;
    cdqX(left, mid, ops, answers);
    cdqX(mid + 1, right, ops, answers);

    int i = left, j = mid + 1, k = left;
    while (i <= mid && j <= right) {
        if (ops[i].x < ops[j].x || (ops[i].x == ops[j].x && ops[i].type < ops[j].type)) {
            tempOps[k] = ops[i];
            tempOps[k++].isActive = true;
            i++;
        } else {
            tempOps[k] = ops[j];
            tempOps[k++].isActive = false;
            j++;
        }
    }
    while (i <= mid) {
        tempOps[k] = ops[i];
        tempOps[k++].isActive = true;
        i++;
    }
    while (j <= right) {
        tempOps[k] = ops[j];
        tempOps[k++].isActive = false;
        j++;
    }
    for (int p = left; p <= right; ++p) ops[p] = tempOps[p];
    
    cdqY(left, right, ops, answers);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int dimX, dimY, q;
    if (!(cin >> dimX >> dimY >> dimZ >> q)) return 0;

    dimX++; dimY++; dimZ++;
    vector<Operation> ops(q + 1);
    vector<int> answers(q + 1, INF);
    vector<int> originalTypes(q + 1);
    
    for (int i = 1; i <= q; ++i) {
        cin >> ops[i].type >> ops[i].x >> ops[i].y >> ops[i].z;
        ops[i].id = i;
        originalTypes[i] = ops[i].type;
    }

    bitTree.assign(dimZ + 2, 0);
    tempOps.resize(q + 1);

    int dx[] = {1, 1, 1, 1, -1, -1, -1, -1};
    int dy[] = {1, 1, -1, -1, 1, 1, -1, -1};
    int dz[] = {1, -1, 1, -1, 1, -1, 1, -1};

    for (int dir = 0; dir < 8; ++dir) {
        for (int i = 1; i <= q; ++i) {
            int nx = (dx[dir] == 1) ? ops[i].x : (dimX - ops[i].x);
            int ny = (dy[dir] == 1) ? ops[i].y : (dimY - ops[i].y);
            int nz = (dz[dir] == 1) ? ops[i].z : (dimZ - ops[i].z);
            
            ops[i].x = nx; ops[i].y = ny; ops[i].z = nz;
            ops[i].val = nx + ny + nz;
            ops[i].isActive = false;
        }
        
        fill(bitTree.begin(), bitTree.end(), 0);
        
        sort(ops.begin() + 1, ops.end(), [](const Operation& a, const Operation& b) {
            return a.id < b.id;
        });
        
        cdqX(1, q, ops, answers);
    }

    for (int i = 1; i <= q; ++i) {
        if (originalTypes[i] == 2) {
            cout << answers[i] << "\n";
        }
    }
    
    return 0;
}

在上述 CDQ 分治代码中，为了保持时间序，我们在每次坐标翻转后重新按原始 ID 排序。通过分离维度的处理，将三维问题降维至一维树状数组，从而在受限的内存环境下完成计算。