레이팅 미적용あなたはタイル1 からタイルN までの番号が付けられているN 枚のタイルを持っている.各タイルの表
面の色と裏面の色は黒色または白色である.ここで,黒色は文字‘B’ で表し,白色は文字‘W’ で表すことに
する.タイルi (1 ≦i ≦N) の表面の色は,文字列S のi 文字目で表される色である.タイルi (1 ≦i ≦N)
の裏面の色は,文字列T のi 文字目で表される色である.
ウズベキスタンはタイル装飾による歴史的建築で有名な国である.ウズベキスタンのモスクやマドラサを
訪れたあなたはそれらの美しい建築に魅了され,タイルに関する奇妙な機械を購入した.この機械は左側と
右側に台を持ち,それぞれの台に1 枚ずつタイルを置くことで,置いた2 枚のタイルと引き換えに新しい
タイルを1 枚受け取ることができる.左側の台に置いたタイルをa,右側の台に置いたタイルをb としたと
き,2 枚のタイルa, b と引き換えに受け取ることができる新しいタイルc は以下の条件を満たす.
• c の表面の色は,a の裏面の色とb の表面の色が同じとき黒色であり,そうでないとき白色である.
• c の裏面の色は,a の表面の色とb の裏面の色が同じとき黒色であり,そうでないとき白色である.
あなたはN 枚のタイルと奇妙な機械を用いて,Q 日間にわたり次のような行動を行うことにした.j 日
目(1 ≦j ≦Q) に行う行動は以下のパターン1 かパターン2 のいずれかである.
• パターン1:タイルXj の表面の色を文字Y j で表される色に変更する.また,タイルXj の裏面の色
を文字Zj で表される色に変更する.ただし,Yj, Zj は‘B’, ‘W’ のいずれかである.
• パターン2:タイルL j, Lj + 1, . . . , R j をこの順に左から右へ一列に並べる.この列に対して,以下の
操作を0 回以上Rj −L j 回以下の好きな回数行うことで,列の中で表面が白色であるタイルをちょう
どM j 枚にできるかを判定する思考実験を行う.
◦列の中で隣り合う2 枚のタイルを選んでそれらを列から取り除く.選んだ2 枚のタイルのうち,
列において左側に置かれていたタイルを機械の左側の台に置き,右側に置かれていたタイルを機
械の右側の台に置くことで,置いた2 枚のタイルと引き換えに新しいタイルを受け取る.そし
て,列の中で元々2 枚のタイルがあった場所に,受け取った1 枚のタイルを入れる.
タイルの情報と行動の情報が与えられたとき,パターン2 の行動の結果を求めるプログラムを作成せよ.
The 25th Japanese Olympiad in Informatics (JOI 2025/2026)
Semifinal Stage
February 1, 2026 (Shimbashi, Tokyo)
• 1 ≦N ≦300 000.
• S は‘B’, ‘W’ からなる長さN の文字列である.
• T は‘B’, ‘W’ からなる長さN の文字列である.
• 1 ≦Q ≦300 000.
• Pj は1, 2 のいずれかである(1 ≦j ≦Q).
• Pj = 1 のとき,1 ≦Xj ≦N (1 ≦j ≦Q).
• Pj = 1 のとき,Y j は‘B’, ‘W’ のいずれかである(1 ≦j ≦Q).
• Pj = 1 のとき,Z j は‘B’, ‘W’ のいずれかである(1 ≦j ≦Q).
• Pj = 2 のとき,1 ≦Lj ≦Rj ≦N (1 ≦j ≦Q).
• Pj = 2 のとき,0 ≦M j ≦R j −Lj + 1 (1 ≦j ≦Q).
• N, Q, Pj, X j, Lj, Rj, M j はすべて整数である.
- (6 点) N ≦6.
- (10 点) N ≦100,Pj = 2 (1 ≦j ≦Q).
- (9 点) N ≦500,Pj = 2 (1 ≦j ≦Q).
- (8 点) N ≦1 700,Pj = 2 (1 ≦j ≦Q).
- (23 点) N ≦10 000,Q ≦10 000.
- (14 点) N ≦100 000,Q ≦100 000.
- (30 点) 追加の制約はない.
The 25th Japanese Olympiad in Informatics (JOI 2025/2026)
Semifinal Stage
February 1, 2026 (Shimbashi, Tokyo)
入力は以下の形式で標準入力から与えられる.
N
S
T
Q
(Query 1)
(Query 2)
...
(Query Q)
各(Query j) (1 ≦j ≦Q) にはいくつかの整数や文字が空白区切りで書かれている.そのうち最初に書か
れているものは整数1, 2 のいずれかであり,これをPj とすると,この行の内容は以下のいずれかである.
• Pj = 1 のとき,この行には続いて1 個の整数Xj と2 個の文字Yj, Zj がこの順に書かれている.これ
はあなたがj 日目に取る行動がパターン1 であり,タイルXj の表面の色を文字Yj で表される色に
変更し,タイルXj の裏面の色を文字Z j で表される色に変更することを表す.ただし,Y j, Zj は‘B’,
‘W’ のいずれかである.
• Pj = 2 のとき,この行には続いて3 個の整数Lj, Rj, M j がこの順に書かれている.これはあなたがj
日目に取る行動がパターン2 であり,タイルLj, Lj + 1, . . . , R j をこの順に左から右へ一列に並べ,こ
の列に対して操作を行い,列の中で表面が白色であるタイルをちょうどM j 枚にすることができるか
を判定する思考実験を行うことを表す.
P j = 2 となるj (1 ≦j ≦Q) それぞれに対して,列の中で表面が白色であるタイルをちょうどM j 枚にす
ることができるときYes を,そうでないときNo を,j の昇順に改行区切りで出力せよ.
The 25th Japanese Olympiad in Informatics (JOI 2025/2026)
Semifinal Stage
February 1, 2026 (Shimbashi, Tokyo)
4
WBWB
BWBB
5
2 3 4 1
2 1 2 0
1 3 B B
2 3 4 2
2 2 4 1
Yes
Yes
No
Yes
6
BWBWWB
WBWBBB
8
2 1 3 2
2 2 6 0
2 1 5 3
2 3 3 0
2 3 4 1
2 5 6 2
2 2 6 4
2 1 4 2
No
Yes
Yes
Yes
Yes
No
No
Yes