Consider determining whether block \(A\) exists at time \(T\). Suppose that block \(A\) is the \(c_A\)-th block from the bottom within the \(X_A\)-th column. Then, block \(A\) disappears when the bottom-row blocks disappear for the \(c_A\)-th time. Thus, once we can enumerate the timestamps \(d_1 < d_2 < \dots\) when the bottom-row blocks vanish, then the problem can be solved by comparing \(T\) and \(d_{c_A}\). (If the block never disappears more than \(c_A\) times, let \(d_{c_A} = \infty\).)

We will find the times \(d_1 < d_2 < \dots\) when the block will disappear. \(d_c\) is the maximum of the timestamp on which the \(c\)-th block from the bottom within each column reaches the bottommost row. If any column does not have \(c\) or more blocks, then \(d_c=\infty\).

\(d_1\) can be found as the maximum value of the time when the bottommost block in each column reaches the bottommost row, plus \(1\). If the \(c\)-th block from the bottom within the \(x\)-th row is initially located at cell \((x,y_{x,c})\), we have \(d_1 = \max\{y_{1,1},\dots,y_{W,1}\}\).

Next, we will find \(d_c \; (c \geq 2)\). Consider the time when the \(c\)-th block from the bottom within the \(x\)-th row reaches the bottommost row. If the block is never obstructed by the block below before reaching the bottommost row, then the block reaches the bottommost row at time \(y_{x,c}-1\). If it is obstructed, then afterward the \(c\)-th block goes down by one cell every time the \((c-1)\)-th block goes down, and it reaches the bottommost row at time \(d_{c-1}\), when the \((c-1)\)-th block vanishes. Thus, \(d_c=\max\{y_{1,c},\dots,y_{W,c},d_{c-1}+1\}\).

Therefore, \(d\) can be found by the following algorithm:

• Initialize \(d_1,d_2,\dots\), and \(d_{N+1}\) with \(0\).
• For each \(x=1,\dots,W\), do the following:
  • Sort the \(y\) coordinates of the blocks in the \(x\)-th column. Let \(y_{x,1} < y_{x,2} < \dots,y_{x,C}\) be the coordinates.
  • For each \(c=1,\dots,C\), set \(d_c \leftarrow \max\{d_c,y_{x,c}\}\).
  • Set \(d_{C+1} \leftarrow \infty\).
• For each \(c=2,\dots,N+1\), set \(d_c\leftarrow \max\{d_c,d_{c-1}+1\}\).

This algorithm runs in \(O(N\log N)\), where the sorting is the bottleneck. Once we have found \(d\), each query can be answered in \(O(1)\) time, so the overall time complexity is \(O(N\log N + Q)\).

Sample code (Python)