AGC059 A - My Last ABC Problem (500)
解説の解法
文字列は円環状に繋がっていると考えると区間は両端を含んで選んで考えても良くなる
実際の操作は選んでない方にすることとする
異なる文字が連続している部分が$ k箇所あれば答えは$ \left \lceil \frac{k}{2} \right \rceil
同じ文字列間の所で置換すると$ kが1操作で2減る
ABxxxBAでもABxxxABでも左右の端以外の文字列内でABを逆にすれば2減る
同じ文字列のペアが1個ずつになった場合、残り3つなら2回、2つなら1回で終わる
全ての部分文字列で異なる文字が連続している部分がいくつあるか数えると間に合わないので累積和で事前に求めておく
部分文字列の端同士が同じかどうかはクエリ毎に確認が必要