公式解説の

なお、この問題は \( S_i=S_{ i+1}\)であるような\(i\)を順序付き集合などで処理することによっても同様の計算量で解く事ができます。

の部分を解説します。

\(S\)の\(L\)文字目～\(R\)文字目(端を含む)からなる文字列を\(S[L,R]\)と表記します。

また、\(X\)を\(S_i = S_{i+1}\)となる\(i (1 \leq i \leq N-1)\) の集合とします。

\(S[L,R]\)が良い文字列であることと、\(L, L+1,...,R-1\)のいずれも\(X\)に含まれないことが同値な条件となります。

これは例えば\(X\)の元を順序付き集合(C++におけるstd::setなど)で管理し、\(L\)以上の元のうち最も小さい元が\(R\)以上であるかどうか(これはupper_boundなどで判定可能です)を確認すれば十分です。

また、クエリ1が与えられた時、\(S_i = S_{i+1}\)かどうかの関係が変更されるのは\(i=L-1,R\)の2通りしかありません。よって、この2つに対して\(X\)に含まれなければ追加する、含まれていれば削除するという操作をすればよいです。(余談ですが、このように区間に対する操作を境界だけに対する操作に言い換えて計算量を削減するのはしばしば使われるテクニックです)

まとめると以下のような解法でACすることができます。

1. 初期値の\(S\)に対し\(S_i = S_{i+1}\)となる\(i\)からなる集合\(X\)をとる。
2. 各クエリに対して以下の操作を行う。
   1. クエリ1が与えられた時、\(L-1\)が\(X\)に含まれていなければ追加し、含まれていれば削除する。\(R\)に対しても同様の操作を行う。
   2. クエリ2が与えられた時、\(L,L+1,...,R-1\)のいずれも\(X\)に含まれていないことをチェックする。

ACコード (0-indexedになっていることに気をつけてください)

https://atcoder.jp/contests/abc341/submissions/50350339