文字列 \(S[L:R]\) で、 \(S_LS_{L+1}\ldots S_R\) を表します。

• \(S[L:R]\) は文字の昇順に並んでいる （公式解説より）

隣接する \(2\) 文字ごとに確認すれば十分です。隣接する \(2\) 文字に関する判定結果をセグメント木で管理することで、どちらのクエリの場合も \(O(\log N)\) 時間で処理できます。

• \(S[L:R]\) に含まれる最小の文字を \(c\) 、最大の文字を \(d\) としたとき、 \(c\) より大きく \(d\) より小さいすべての文字が、\(S[L:R]\) と \(S\) に同じ個数含まれている（公式解説より）

つまり、 \(c\) より大きく \(d\) より小さいすべての文字は \(S[L:R]\) に収まっている必要があります。よって、各文字種 \(t\) ごとに、 \(t\) が存在する位置の最小値と最大値をセグメント木で管理すれば、出力クエリに対して \(O(\log \sigma)\) 時間で対応できます。更新クエリに対しては、次のようなシミュレーションをする必要があります。

1. 位置 \(x\) の文字が変化する。
2. もともとあった文字種は位置 \(x\) に存在しなくなり、変化後の文字種は位置 \(x\) に存在するようになる。
3. 高々 \(2\) 個の文字種について、その文字が存在する位置の集合が変わるので、従ってその最小値と最大値が変わる。

このシミュレーションは、各文字種 \(t\) について \(t\) が存在する位置の集合を順序付き辞書（ ex. C++ の std::set ）で管理することで、 \(O(\log\sigma + \log N)\) 時間で実現できます。

これで判定に必要な情報がすべて得られました。全体の計算量は、例えば \(O((N+\sigma +Q)(\log N +\log\sigma ))\) です。

実装例 : https://atcoder.jp/contests/abc285/submissions/38078821