隣接している同じ色のマスを連結とみなす連結成分をうまく管理することでこの問題を解くことができます。

ordered set を用いる解法

• 各色のマスが何個あるかを表す配列 \(C\)
• 各連結成分の左端のマスの番号を持つordered set \(S\)
• それらのマスが何色に塗られているかを持つdict \(D\)

の \(3\) つを用意し、クエリごとに更新します。2種類目のクエリは \(C[c]\) を返すだけでよいです。1種類目のクエリは以下のように処理します。

1. \(S\) に含まれる要素のうち、\(x\) 以下の最大の要素を求め \(L\) とする。\(S\) に含まれる要素のうち \(L\) より大きな最小の要素を求め \(R\) とする
   （\(x\) を含む連結成分は右半開区間 \([L,R)\) となる）
2. \(D\) と \(C\) を更新する
   • \(C[D[L]] \leftarrow C[D[L]] - (R-L)\)
   • \(D[L] \leftarrow c\)
   • \(C[D[L]] \leftarrow C[D[L]] + (R-L)\)
3. 左右の連結成分と同じ色になっていれば、境界を取り除く
   • \(D[R]=D[L]\) なら \(S\) から \(R\) を取り除く（右の境界）
   • \(S\) に含まれる要素のうち、\(L\) 未満の最大の要素を求め \(L'\) とする。\(D[L']=D[L]\) なら \(S\) から \(L\) を取り除く（左の境界）

この処理はクエリごとに \(O(\log N)\) で行えることから、全体で \(O(Q\log N)\) でこの問題を解けました。

writer解(C++)

DSU を用いる解法

• 各色のマスが何個あるかを表す配列 \(C\)
• 連結成分を表す情報として、左端のマスの番号、サイズ、色を持つDSU

の2つを用意し、クエリごとに更新します。ordered setを用いた解法同樣、

1. \(x\) を含む連結成分を特定
2. \(C\) 及び連結成分の色を更新
3. 左右の連結成分と同じ色になっていればマージ

の3つを行えば良いです。この処理はクエリあたりならし \(O(\alpha(N))\) で行えることから、全体で \(O(Q \alpha(N))\) でこの問題を解けました。
（\(\alpha\) は逆アッカーマン関数）

writer解(C)