题目链接：nowcoder多校8-Distance

题意：

三维空间内，给定两种操作：

1. 给点(x,y,z)染色。
2. 询问与(x,y,z)点最近的染色点的曼哈顿距离。

题解：

定期重构（很神奇）。

可以先假设，所有询问都在加点之后，我们就可以用bfs预处理出答案，然后O(1)进行查询。

那么我们就可以维护一个集合，每次询问时，我们把查询的点与集合内的染色点进行计算，当集合内的点超过一定数量$E$的时候，用bfs处理出空间中的点到这些染色点的最短距离。

时间复杂度为$O(\frac{qnmh}{E}+qE)$，显然，当$E=\sqrt{nmh}$时，取理论最小值。

参考代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5;
const ll inf = 0x7f7f7f7f7f7f7f7f;
int n, m, h, q;
int threslod;
struct node
{
    int x, y, z;
    node(int a, int b, int c) { x = a, y = b, z = c; };
};
vector<node> tmp;
queue<node> que;
int dis[MAXN<<2];
int cal(int x, int y, int z)
{
    return x * m * h + y * h + z;
}
int nxt[5][10];
int main()
{
    scanf("%d%d%d%d", &n, &m, &h, &q);
    threslod = sqrt(n * m * h);
    memset(dis, 0x3f, sizeof(dis));
    nxt[1][1] = 1, nxt[1][2] = -1, nxt[1][3] = 0, nxt[1][4] = 0, nxt[1][5] = 0, nxt[1][6] = 0;
    nxt[2][1] = 0, nxt[2][2] = 0, nxt[2][3] = 1, nxt[2][4] = -1, nxt[2][5] = 0, nxt[2][6] = 0;
    nxt[3][1] = 0, nxt[3][2] = 0, nxt[3][3] = 0, nxt[3][4] = 0, nxt[3][5] = 1, nxt[3][6] = -1;
    while (q--)
    {
        int op, x, y, z;
        scanf("%d%d%d%d", &op, &x, &y, &z);
        if (op == 1)
        {
            tmp.push_back(node(x, y, z));
            dis[cal(x, y, z)] = 0;
            if (tmp.size() >= threslod)
            {
                for (int i = 0; i < tmp.size(); i++)
                    que.push(tmp[i]);
                tmp.clear();
                while (!que.empty())
                {
                    node now = que.front();
                    int u = cal(now.x, now.y, now.z);
                    que.pop();
                    for (int i = 1; i <= 6; i++)
                    {
                        int tx = now.x + nxt[1][i];
                        int ty = now.y + nxt[2][i];
                        int tz = now.z + nxt[3][i];
                        if (tx < 1 || ty < 1 || tz < 1 || tx > n || ty > m || tz > h)
                            continue;
                        int v = cal(tx, ty, tz);
                        if (dis[v] > dis[u] + 1)
                        {
                            dis[v] = dis[u] + 1;
                            que.push(node(tx, ty, tz));
                        }
                    }
                }
            }
        }
        else
        {
            int u = cal(x, y, z);
            int ans = dis[u];
            for (int i = 0; i < tmp.size(); i++)
                ans = min(ans, abs(x - tmp[i].x) + abs(y - tmp[i].y) + abs(z - tmp[i].z));
            printf("%d\n", ans);
        }
    }
    return 0;
}