Let us say “satisfying the condition for \(i\)” to mean making \(ab \geq S_i\) if \(P_i = 1\), or making \(ab < S_i\) if \(P_i = -1\). For each query, finding the maximum number of \(i\) for which the condition can be satisfied allows us to calculate the answer.

If we can spend \(\Theta(N)\) time per query, we can solve it by simulating a greedy algorithm that acts as follows at each step of the game. Roughly speaking, we “continue to satisfy the condition as much as possible, and when it becomes impossible, replace the value to make the next step favorable.”

• For simplicity, assume the value to be replaced is \(a\).
• If \(P_i = P_{i+1} = 1\), replace \(a\) with \(X\).
• If \(P_i = P_{i+1} = -1\), replace \(a\) with \(1\).
• If \(P_i = 1\) and \(P_{i+1} = -1\), replace \(a\) with \(\displaystyle \left\lceil \frac{S_i}{b} \right\rceil\). If this value exceeds \(X\), replace with \(1\).
• If \(P_i = -1\) and \(P_{i+1} = 1\), replace \(a\) with \(\displaystyle \min \left\{ \left\lfloor \frac{S_i - 1}{b} \right\rfloor , X \right\}\). If this value falls below \(1\), replace with \(X\).

Let \(f(k, x)\) denote “the first position where the condition for \(i\) cannot be satisfied” in the above greedy algorithm when starting the game at \(i = k\) with \(a = b = x\). For each query, the maximum number of \(i\) for which the condition can be satisfied can be found as follows:

• If \(f(l, 1) > r\), the condition can be satisfied for all \(i\).
• Otherwise, let \(l_1 := f(l, 1) + 1\). Hereafter, define \(l_{k+1} = \max \{ f(l_k, 1), f(l_k, X) \} + 1\) inductively. The maximum \(k\) satisfying \(l_k \leq r+1\) equals the number of \(i\) for which the condition cannot be satisfied.

If the values of \(f(k, 1), f(k, X)\) are known for all \(k\), we can answer queries in \(O(\log N)\) using binary lifting. \(f(k, x)\) can be calculated as follows:

• When \(P_k = 1\):
  • If \(xX < S_i\), then \(f(k, x) = k\). Below we consider otherwise.
  • If \(P_{k+1} = 1\), then \(f(k, x) = f(k + 1, X)\).
  • If \(P_{k+1} = -1\), then \( \displaystyle f(k, x) = f \left(k + 1, \left\lceil \frac{S_k}{x} \right\rceil \right)\).
• When \(P_k =-1\):
  • If \(x \geq S_i\), then \(f(k, x) = k\). Below we consider otherwise.
  • If \(P_{k+1} = 1\), then \(\displaystyle f(k, x) = f \left(k + 1, \min \left\{ \left\lfloor \frac{S_k - 1}{x} \right\rfloor , X \right\} \right)\).
  • If \(P_{k+1} = -1\), then \(f(k, x) = f(k + 1, 1)\).

For each \(k\), the values of \(x\) for which we need to compute \(f(k,x)\) are only \(1\), \(X\), and numbers represented as \(\displaystyle \left\lceil \frac{S_{k-1}}{t} \right\rceil, \left\lfloor \frac{S_{k-1} - 1}{t} \right\rfloor\), which is at most \(O(\sqrt{\max S})\).

The necessary values of \(f(k, x)\) can be calculated in \(O(N \sqrt {\max S})\), and each query can be answered in \(O(\log N)\), so we can solve this problem in \(O(N \sqrt {\max S} + Q \log N)\).