公式解説の必要条件を再掲します。

• \(S[L:R]\) は文字の昇順に並んでいる
• \(S[L:R]\) に含まれる最小の文字を \(c\) 、最大の文字を \(d\) としたとき、 \(c\) より大きく\(d\) より小さいすべての文字が、 \(S[L:R]\) と \(S\) に同じ個数含まれている

まず、\(S[L:R]\) が文字の昇順に並んでいるかを確認しましょう。 \(S[L:R]\) が昇順であることを言い換えると、以下のようになります。

• \(S_L \leq S_{L+1} \leq \cdots \leq S_{R}\)

つまり、\(S[L:R]\) が昇順であるか否かは、隣接二項の関係が \(\leq\) である個数が \(R-L\) 個あるかを確認すれば分かります。 これはセグメントツリーを使えば \(O(\log N)\) で求めることができ、更新も隣接2項間だけ見れば良いことから \(O(\log N)\) です。

続いて、\(c\) より大きく\(d\) より小さいすべての文字が、 \(S[L:R]\) と \(S\) に同じ個数含まれているかを判定します。

これは、 \(S[0:L-1] \cup S[R+1:N]\)に\(c\) より大きく\(d\) より小さいすべての文字が含まれていないことと同値です。 これは、文字集合の和集合を取ることができれば良いことが分かります。 そこで、BitSetを用いて和集合をセグメントツリーで計算すれば、更新及び判定が共に \(O(\frac{\sigma}{\mathrm{wordsize}} \log N)\) で求められます。

\(\sigma = 26\) なので、BitSetの代わりにintを用いれば非常に高速になります。