Loop through the blocks and holes after sorting them by the $x$ dimension. Let $dx,dy,dz$ be the distance of a block to a hole in the $x,y,z$ dimension. If you fix $dy$ and $dz$, you can easily find the minimum $dx$ using a range minimum query. To do this range minimum query you can use a segment tree for one dimension and cdq for another. Since you don't know $dy$ and $dz$ yet, you can binary search for them. Now you have 4 log factors. You can remove 2 log factors by incorporating the binary search into your segment tree and cdq using something resembling a segment tree walk, always making sure the value you are binary searching matches a boundary of your segment tree or cdq function call.

Time complexity: $\mathcal{O}((n+q){\log }^2(n+q))$

Richard: apparently turning the first dim segtree into a parallel binary search significantly improves runtime. I think it's because memory goes from $n\log n$ to $n$. I'm unable to get similar gains by turning the 2nd level into recursive though (that seems in line with 1D seg and div-conquer doing similarly).

The other optimization is to initialize the event queues using sorted arrays. Not doing this seems to increase my code's runtime by about 50% or so: the segtree itself is actually quite fast (due to being memory efficient I guess).