ABC 401-500/ABC411C - Black Intervals - 競技プログラミング用 知識集積所

---

問題

ABC411C

必要知識

B以下レベルの内容は省略

• 特になし

考え方

nが小さければ愚直にやって簡単だが、nが大きいと余裕のTLE。
よって、高速化を考える。
ポイントは、前のクエリとほとんど状況が変わらないこと。
つまり、前回からの何らかの差分だけ追っていく方針を考えたい。

また、連続区間が何個あるかを数えるには、

• 区間の左端の数を数える
• 区間の右端の数を数える
• 区間の両端の数を数えて2で割る

といった方法がある。
今回でいえば区間の両端とは色の境目であるため、「色の境目がどこにあるか」を前のクエリとの差分を取ることが考えられる。

現在の色の境目をset（未作成）で管理し、指定場所の左右隣との関係を「set（未作成）の中にいるなら消す、いないなら加える」としておけばよい。
境界数を.size()で取得し、2で割ったものが答え。

解答例

解答例

注意点

別解