Distance

Posted on | In , , ,

题目链接

题意

三维空间中每次会标记一个点，也会询问某个点$(x,y,z)$距离标记点距离最近是多少。

思路

定期重构

因为被标记的点不会再删除，所以我们可以考虑设置一个$limit$，当标记点数大于这个上限时，我们对这些点统一跑一遍bfs。
查询的时候，一部分要考虑已经跑出bfs的点，另一部分是现在还没重构的点。
当我们设置$limit$，每次bfs复杂度为，总复杂度。
设置最好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifndef ONLINE_JUDGE
#define dbg(x...) do{cout << "\033[33;1m" << #x << "->" ; err(x);} while (0)
void err(){cout << "\033[39;0m" << endl;}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x){for (auto v: a) cout << v << ' '; err(x...);}
template<typename T, typename... A>
void err(T a, A... x){cout << a << ' '; err(x...);}
#else
#define dbg(...)
#endif
#define inf 1ll << 50
struct point
{
	int x, y, z;
};
const int N = 1e5 + 5;
vector<vector<vector<int> > > dis;
vector<point> wait;
queue<point> que;

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

void bfs(int n, int m, int h)
{
	while (!que.empty())
	{
		point f = que.front();
		que.pop();
		for (int dir = 0; dir < 6; dir++)
		{
			int tx = f.x + dx[dir], ty = f.y + dy[dir], tz = f.z + dz[dir];
			if (tx > n || tx < 1 || ty > m || ty < 1 || tz > h || tz < 1)
				continue;
			if (dis[tx][ty][tz] > dis[f.x][f.y][f.z] + 1)
			{
				dis[tx][ty][tz] = dis[f.x][f.y][f.z] + 1;
				que.push((point){tx, ty, tz});
			}
		}
	}
}

int main()
{
	int n, m, q, h;
	scanf("%d%d%d%d", &n, &m, &h, &q);
	dis.resize(n + 1);
	for (int i = 1; i <= n; i++)
	{
		dis[i].resize(m + 1);
		for (int j = 1; j <= m; j++)
		{
			dis[i][j].resize(h + 1);
			for (int k = 1; k <= h; k++)
				dis[i][j][k] = 0x3f3f3f3f;
		}
	}
	int lim = (int)sqrt(n * m * h);
	int cur = 0;
	while (q--)
	{
		int op;
		scanf("%d", &op);
		if (op == 1)
		{
			int x, y, z;
			scanf("%d%d%d", &x, &y, &z);
			cur++;
			wait.push_back((point){x, y, z});
			if (cur > lim)
			{
				while (!que.empty())
					que.pop();
				for (auto &p : wait)
				{
					dis[p.x][p.y][p.z] = 0;
					que.push(p);
				}
				bfs(n, m, h);
				wait.clear();
				cur = 0;
			}
		}
		else
		{
			int x, y, z;
			scanf("%d%d%d", &x, &y, &z);
			int ret = dis[x][y][z];
			for (auto &p : wait)
			{
				ret = min(ret, abs(p.x - x) + abs(p.y - y) + abs(p.z - z));
			}
			printf("%d\n", ret);
		}
	}
	return 0;
}

三维树状数组

另一个思路是以这个立方体的8个顶点，分别开树状数组，记录前缀最值。
以8个方向分别做，可以去掉绝对值，据说常数很小（待补

0%