【典型90問】084 - There are two types of characters（★3）

問題リンク

解法

解説スライドで紹介されていた解法とは違う方法で解いた。(解法2に少し似ているかも)

既にoxが含まれている区間を、右左どちらに広げても必ずoxが含まれることがわかる。
線形時間で問題を解きたいので、lかrを固定したい。今回はlを固定してみることにする。
lを固定した時にoxが含まれる最小のrが分かれば、それ以上にrを大きくしても必ずoxを含む。
後はこの最小のrを高速に求めることができればいいのだが、これはそれぞれの文字が前から何番目のoもしくはxかを先に計算しておくことで実現できる。

---

実装

void solve(long long N, std::string S) {
    ll ans = 0;
    vector<ll> o(N+1, N), x(N+1, N);

    // oi: 前から何番目のoかをカウント
    // xi: 前から何番目のxかをカウント
    ll oi = 0, xi = 0;
    REP (i, N) {
        if (S[i] == 'o') {
   　　 // 前からoi番目のoの位置を保存
            o[oi] = i;
            oi++;
        } else {
            // 前からxi番目のxの位置を保存
            x[xi] = i;
            xi++;
        }
    }

    // 区間の左端を固定, l=i
    oi = 0, xi = 0;
    REP (i, N) {
        if (S[i] == 'o') {
            // x[xi]にはlより大きい、最小の'x'がどこかを保持している
            ans += N - x[xi];
            oi++;
        } else {
            ans += N - o[oi];
            xi++;
        }
    }

    c(ans)
}