遅延セグ木ですか?
前後の文字が違うかどうかで考察する典型テクをセグ木に乗せるだけでは?