典型90問 084 問題文 o と x からなる長さ N の文字列 S が与えられます。 以下の条件をすべて満たす整数の組 (l,r) の個数を求めてください。 1≤l≤r≤N S の l 文字目から r 文字目までの区間に、o と x 両方が含まれる 制約 1≤N≤106 S は o, x からなる長さ N の文字列である 考えたこと 二重ループで愚直に探すのは制約上不可能なので、 ランレングス圧縮で同一マークがどれだけ続いているか調べ、 調べあげた文字数と、それ以降の残数から導く方法をとった。 調べあげた文字数は、l に該当し圧縮処理が途切れた、つまり別のマーク(r に該当)に、 出会った…