現代的な機械(Modern Machine)

ビ太郎は,誕生日プレゼントとしてJOI マシンをもらった.JOI マシンは,1 個のボール,N 個のライ
トタイル,M 個のボタンからなる.ライトタイルにはそれぞれ1 からN までの番号が付けられており,電
源を入れると,ライトタイルi (1 ≦i ≦N) は色Ci (青(B),赤(R) のいずれか) で光るようになっている.ま
た,ボタンにはそれぞれ1 からM までの番号が付けられており,ボタンj (1 ≦j ≦M) を押すと,次のよう
なことが起こる.
1. ライトタイルAj の上にボールが置かれる.
2. ライトタイルAj の色が(元の色にかかわらず) 赤になる.
3. ボールが取り除かれるまで,以下のことが繰り返し行われる.
今,ボールが置かれているライトタイルの番号をp とする.
ライトタイルp の色が青の場合
ライトタイルp の色が赤に変わる.その後,もしp = 1 の場合はボールが取り除かれ,そう
でない場合はボールがライトタイルp −1 の上に移動する.
ライトタイルp の色が赤の場合
ライトタイルp の色が青に変わる.その後,もしp = N の場合はボールが取り除かれ,そ
うでない場合はボールがライトタイルp + 1 の上に移動する.
JOI マシンに興味を持ったビ太郎は,Q 回の実験を計画している.k 回目(1 ≦k ≦Q) の実験は,JOI マシ
ンの電源を入れた後,ボタンLk, Lk + 1, . . . , Rk をこの順に押すというものである.ただし,ボールが取り除
かれるまでは,次のボタンを押さずに待つものとする.
JOI マシンの情報および実験の情報が与えられるので,それぞれの実験について,実験が終わった後にお
ける,色が赤であるようなライトタイルの個数を求めるプログラムを作成せよ.

第22 回日本情報オリンピック(JOI 2022/2023) 本選
2023 年2 月12 日(オンライン開催)

• 3 ≦N ≦120 000.
• 1 ≦M ≦120 000.
• Ci (1 ≦i ≦N) はB またはR である.
• 1 ≦Aj ≦N (1 ≦j ≦M).
• 1 ≦Q ≦120 000.
• 1 ≦Lk ≦Rk ≦M (1 ≦k ≦Q).
• N, M, Aj, Q, Lk, Rk は整数である.

第22 回日本情報オリンピック(JOI 2022/2023) 本選
2023 年2 月12 日(オンライン開催)

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

第22 回日本情報オリンピック(JOI 2022/2023) 本選
2023 年2 月12 日(オンライン開催)

入力は以下の形式で標準入力から与えられる.
N M
C1C2 · · ·CN
A1 A2 · · · AM
Q
L1 R1
L2 R2
...
LQ RQ

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

생성자가 기록되지 않았습니다.

출처 JOI 2023 Final