题意：
在一个三维空间中，给出q次操作，每次操作可以在空间中加上一个固定点，或者询问一个点，对于一个询问操作，输出距离这个点最近的固定点的曼哈顿距离。
思路：
官方题解：先假设所有询问都在加标记之后，那么我们可以同过一次bfs求出网格中每个点离最近标记点的距离，询问就可以O（1）回答。
现在考虑定期重构处理增量标记，记一个新增标记队列，每次拿出bfs预处理之后的结果，在暴力枚举队列中每一个新标记，这些结果取个min即可。
当队列元素超过一个阈值E时，我们把队列中的标记也进行bfs，更新每个位置的答案，清空新增标记队列。
克制复杂度是O（qnmh/E+qE），当E=根号nmh时取最小。
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;i++) #define dep(i,b,a) for(int i=b;i>=a;i--) #define clr(a,b) memset(a,b,sizeof(a)) #define pb push_back #define pii pair<int,int > using namespace std; const int maxn=100010; const int inf=0x3f3f3f3f; int dis[maxn]; int n,m,h; int getid(int x,int y,int z){ return (x-1)*m*h+(y-1)*h+z; } int dir[6][3]={{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}}; struct node{ int x,y,z; }; int getdis(node a,node b){ return abs(a.x-b.x)+abs(a.y-b.y)+abs(a.z-b.z); } vector<node >ve; queue<node >q; int main(){ int qi; cin>>n>>m>>h>>qi; int sq=sqrt(1ll*n*m*h); int si=0; clr(dis,inf); rep(i,1,qi){ int op,x,y,z; scanf("%d%d%d%d",&op,&x,&y,&z); if(op==1){ ve.pb({x,y,z}); si++; if(si==sq){ rep(i,0,si-1){ q.push(ve[i]); dis[getid(ve[i].x,ve[i].y,ve[i].z)]=0; } while(!q.empty()){ node st=q.front(); q.pop(); rep(i,0,5){ int xx=st.x+dir[i][0]; int yy=st.y+dir[i][1]; int zz=st.z+dir[i][2]; if(xx<1||xx>n||yy<1||yy>m||zz<1||zz>h)continue; if(dis[getid(xx,yy,zz)]>dis[getid(st.x,st.y,st.z)]+1){ dis[getid(xx,yy,zz)]=dis[getid(st.x,st.y,st.z)]+1; q.push({xx,yy,zz}); } } } ve.clear(); si=0; } }else{ int ans=dis[getid(x,y,z)]; rep(i,0,si-1){ ans=min(ans,getdis({x,y,z},ve[i])); } printf("%d ",ans); } } }