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).