题目链接:nowcoder多校8-Distance
题意:
三维空间内,给定两种操作:
- 给点(x,y,z)染色。
- 询问与(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;
}