\(P_i = 1\) なら \(ab \geq S_i\) にすることを、\(P_i = -1\) なら \(ab < S_i\) にすることを「\(i\) について条件を満たす」ということにします。各クエリについて、条件を満たすことのできる \(i\) の個数の最大値を求めれば答えが計算できます。

\(1\) つのクエリあたり \(\Theta(N)\) かけてよい場合は、ゲームの各ステップで以下のように行動する貪欲法をシミュレーションすることで解くことができます。大雑把に言うと「なるべく条件を満たし続け、不可能になったら次のステップにおいて都合が良くなるように値を置き換える」ということを行います。

• 簡単のため、置き換える値が \(a\) であるとする。
• \(P_i = P_{i+1} = 1\) なら \(a\) を \(X\) で置き換える。
• \(P_i = P_{i+1} = -1\) なら \(a\) を \(1\) で置き換える。
• \(P_i = 1\) かつ \(P_{i+1} = -1\) なら、\(a\) を \(\displaystyle \left\lceil \frac{S_i}{b} \right\rceil\) で置き換える。この値が \(X\) を超える場合は \(1\) で置き換える。
• \(P_i = -1\) かつ \(P_{i+1} = 1\) なら、\(a\) を \(\displaystyle \min \left\{ \left\lfloor \frac{S_i - 1}{b} \right\rfloor , X \right\}\) で置き換える。この値が \(1\) を下回る場合は \(X\) で置き換える。

\(i = k\) で \(a = b = x\) としてゲームを開始したときに、上記の貪欲法において「初めて \(i\) についての条件を満たせなくなる位置」を \(f(k, x)\) とおきます。各クエリについて、条件を満たすことのできる \(i\) の個数の最大値は以下のように求めることができます。

• \(f(l, 1) > r\) なら全ての \(i\) について条件を満たせる。
• そうでないとき、\(l_1 := f(l, 1) + 1\) とおく。以降、\(l_{k+1} = \max \{ f(l_k, 1), f(l_k, X) \} + 1\) と帰納的に定める。\(l_k \leq r+1\) を満たす最大の \(k\) が、条件を満たすことができない \(i\) の個数に等しい。

全ての \(k\) について \(f(k, 1), f(k, X)\) の値が分かれば、ダブリングによってクエリに \(O(\log N)\) で答えられます。\(f(k, x)\) は次のように計算することができます：

• \(P_k = 1\) のとき：
  • \(xX < S_i\) なら \(f(k, x) = k\) である。以下そうでない場合を考える。
  • \(P_{k+1} = 1\) なら \(f(k, x) = f(k + 1, X)\) である。
  • \(P_{k+1} = -1\) なら \( \displaystyle f(k, x) = f \left(k + 1, \left\lceil \frac{S_k}{x} \right\rceil \right)\) である。
• \(P_k =-1\) のとき：
  • \(x \geq S_i\) なら \(f(k, x) = k\) である。以下そうでない場合を考える。
  • \(P_{k+1} = 1\) なら \(\displaystyle f(k, x) = f \left(k + 1, \min \left\{ \left\lfloor \frac{S_k - 1}{x} \right\rfloor , X \right\} \right)\) である。
  • \(P_{k+1} = -1\) なら \(f(k, x) = f(k + 1, 1)\) である。

各 \(k\) について、\(f(k,x)\) を計算しなければならない \(x\) は、 \(1, X\) および \(\displaystyle \left\lceil \frac{S_{k-1}}{t} \right\rceil, \left\lfloor \frac{S_{k-1} - 1}{t} \right\rfloor\) と表される数のみであり、これは高々 \(O(\sqrt{\max S})\) 個です。

\(f(k, x)\) のうち必要な値は \(O(N \sqrt {\max S})\) で計算でき、各クエリには \(O(\log N)\) で答えられるので、\(O(N \sqrt {\max S} + Q \log N)\) でこの問題を解くことができました。