現代的な機械 (Modern Machine)

ビ太郎は，誕生日プレゼントとして JOI マシンをもらった． JOI マシンは，\(1\) 個の ボール，\(N\) 個の ライトタイル，\(M\) 個の ボタン からなる． ライトタイルにはそれぞれ \(1\) から \(N\) までの番号が付けられており， 電源を入れると，ライトタイル \(i\) (\(1 \leqq i \leqq N\)) は色 \(C_i\) (青 (B)，赤 (R) のいずれか) で光るようになっている． また，ボタンにはそれぞれ \(1\) から \(M\) までの番号が付けられており， ボタン \(j\) (\(1 \leqq j \leqq M\)) を押すと，次のようなことが起こる．

1. ライトタイル \(A_j\) の上にボールが置かれる．
2. ライトタイル \(A_j\) の色が (元の色にかかわらず) 赤になる．

3. ボールが取り除かれるまで，以下のことが繰り返し行われる．

   今，ボールが置かれているライトタイルの番号を \(p\) とする．

   ライトタイル \(p\) の色が青の場合

   ライトタイル \(p\) の色が赤に変わる．その後，もし \(p=1\) の場合はボールが取り除かれ，そうでない場合はボールがライトタイル \(p-1\) の上に移動する．

   ライトタイル \(p\) の色が赤の場合

   ライトタイル \(p\) の色が青に変わる．その後，もし \(p=N\) の場合はボールが取り除かれ，そうでない場合はボールがライトタイル \(p+1\) の上に移動する．

JOI マシンに興味を持ったビ太郎は，\(Q\) 回の実験を計画している． \(k\) 回目 (\(1 \leqq k \leqq Q\)) の実験は，JOI マシンの電源を入れた後，ボタン \(L_k, L_k+1, \ldots, R_k\) をこの順に押すというものである． ただし，ボールが取り除かれるまでは，次のボタンを押さずに待つものとする．

JOI マシンの情報および実験の情報が与えられるので， それぞれの実験について，実験が終わった後における，色が赤であるようなライトタイルの個数を求めるプログラムを作成せよ．

入力は以下の形式で標準入力から与えられる．

\(N\) \(M\)
\(C_1C_2 \cdots C_N\)
\(A_1\) \(A_2\) \(\cdots\) \(A_M\)
\(Q\)
\(L_1\) \(R_1\)
\(L_2\) \(R_2\)
\(\vdots\)
\(L_Q\) \(R_Q\)

標準出力に \(Q\) 行出力せよ． \(k\) 行目 (\(1 \leqq k \leqq Q\)) には，\(k\) 回目の実験が終わった後における，色が赤であるようなライトタイルの個数を出力せよ．

• \(3 \leqq N \leqq 120\,000\)．
• \(1 \leqq M \leqq 120\,000\)．
• \(C_i\) (\(1 \leqq i \leqq N\)) は B または R である．
• \(1 \leqq A_j \leqq N\) (\(1 \leqq j \leqq M\))．
• \(1 \leqq Q \leqq 120\,000\)．
• \(1 \leqq L_k \leqq R_k \leqq M\) (\(1 \leqq k \leqq Q\))．
• \(N, M, A_j, Q, L_k, R_k\) は整数である．

1. (\(3\) 点) \(N \leqq 300\)，\(M \leqq 300\)，\(Q = 1\)．
2. (\(12\) 点) \(N \leqq 7\,000\)，\(M \leqq 7\,000\)，\(Q = 1\)．
3. (\(10\) 点) \(Q \leqq 5\)．
4. (\(11\) 点) \(N = 10\)，\(C_i\) は R である (\(1 \leqq i \leqq N\))．
5. (\(26\) 点) \(i \leqq t\) ならば \(C_i\) が R であり，\(i > t\) であれば \(C_i\) が B であるような整数 \(t\) (\(0 \leqq t \leqq N\)) が存在する．
6. (\(17\) 点) \(A_j \leqq 20\) または \(A_j > N - 20\) (\(1 \leqq j \leqq M\))．
7. (\(21\) 点) 追加の制約はない．

JOI 2023 · JCIOI · CC BY-SA 4.0