Codeforces Round #754 (Div. 2) C. Dominant Character ～ SparseTableを用いた条件を満たす最小の区間の存在可能性と二分探索

https://codeforces.com/contest/1605/problem/C

明らかにtoo muchな解法ですが、考え方としては悪くないのでこれを記します。

# 題意
- a,b,c からなる n文字の文字列があります。
- 次の条件を満たす"2文字以上の"最短の連続区間の長さを答えてください。存在しない場合は-1を答えます。
    - その区間のaの数は、その区間のb および cの数と厳密に大きい

# 例 および 一般的な答え O(N)
実は、以下の文字列が存在するかを答えればよいです。

- 2文字 `aa`
- 3文字 `aba` `aca`
- 4文字 `abca` `acba`
- 5文字 `abaca` `acaba`
- 7文字 `abbacca` `accabba`

# 自分の考え方 O(NlogN)

まず、題意からして、`始点終点がaである文字列が最短の区間`だとします。なぜなら、始点終点がaでない文字列が答えだとするなら、両端の`b, c`を削った文字列も必ず条件を満たしそれが答えになります。

以下のような図を描き、じっと睨みます。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/30938/cb422190-e6a6-c90e-a193-23186691eb21.png)

CountA,B,Cは最初からそこまでに出現した文字の数。a-bなどはそれぞれ、aからb,cを引いた文字です。すると、成立する区間とは、ある始点を決めて`a-b, a-c`を得たとき、次の文字以降で両者がそれ以上になるとき、に条件を満たします。

- 例えば: index[0,3]の区間は`1,1`からスタートし、index3の`1,1`の区間で条件を満たします。index12,14,20,21,22も条件を満たしますが、index3までが最短の区間です。
- 例えば: index[14,20]の区間は`1,2`からスタートし、index20の区間で条件を満たします。

あらかじめ、累積和を取っておくことで、ある始点と終点を決めたときに条件を満たすかは上記のようにa,b,cの数をカウントしておくことでO(1)で可能です。そこで、すべての文字の"a"の区間を探索すれば答えが出そうですが、それでは$O(N^2)$になってしまいます。

二分探索が使えないかを考えてみます。まず、存在の可能性は線形に変化しません。例えば、
`[a]bababba[a]{a}{a}bbbbbabbbaaa{a}{a}...`
という文字で、最初の`[a]`から成立する区間を求めたい場合、次の`[a]`の区間を求めたいですが、他に`{a}`の区間でも成立します。が、括弧のない`a`では成立しません。つまり、成立する区間が離れているため、二分探索ができません。

そこで、SparseTableを用いることにします。これは、事前計算$O(NlogN)$でmaxやminのクエリを$O(N)$でできるデータ構造です。持たせるテーブルは、`a-b`と`a-c`で、maxをとります。

これにより、二分探索を用いたクエリが可能になります。あるaを始点として、そのあとに答えがあるかを確認したいとします。そのa+1の位置から、二分探索で今の`a-b`と`a-c`以上の値となる区間を探します。もし、クエリでこの条件を満たす場合、区間のmaxを取っているため、その位置、あるいは、それよりも短い場所で`条件を満たす可能性があります`。

さて、条件を満たす`可能性がある`といったのには理由があります。次の場合を考えます。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/30938/082fa96f-91ac-c845-8ea7-628c3fa19cd0.png)
今、index0にいたとして、(index1から)index8までのクエリをすると`a-b`はindex1で, `a-c`はindex5,6でmaxとなる1です。ところが、この区間において、初期位置の`a-b`と`a-c`以上の値を`同時に`満たしている区間はありません。このため、区間のMaxはあくまで`可能性がある`は分かるものの、`ある`とは言えません。

しかしながら、これでO(NlogN)で答えを得ることができました。

# 実装

```C++
void solve(){
    // O(NlogN * k) : kは出現しうる文字の種類。今回は2固定。
    int n; cin >> n;
    string s; cin >> s;
    vector<int> diffb(n), diffc(n), posa;
    int numa = 0, numb=0, numc=0;
    REP(i, s.size()){
        if(s.at(i) == 'a') {
            ++numa;
            posa.emplace_back(i); // トリガとなる位置は覚えておく
        }
        else if(s.at(i) == 'b') ++numb;
        else if(s.at(i) == 'c') ++numc;
        diffb.at(i) = numa - numb; // ここまでに出現した a - b を配列に入れる
        diffc.at(i) = numa - numc;
    }
    // SparseTableで、ある区間[l, r)に対する"a -b"などの maxをクエリできるようにする
    auto op = [] (int a, int b) {return max(a,b);};
    SparseTable<int> stb(diffb, op);
    SparseTable<int> stc(diffc, op);
    int ans = 1e9;
    // 全てのlを始点として
    REP(l, posa.size()) {
        int mid;
        int ng = l;
        int ok = posa.size(); // そのあとの全てのaに対して
        while (abs(ok - ng) > 1) {
            mid = (ok + ng) / 2;
            // 少なくとも、選んだmidまでの間に答えの候補があることが考えられて
            // lからmidの間に、lの瞬間のb,cの差分以上のaのポイントがあるなら希望をもって二分探索したい
            if (stb.query(posa.at(l)+1, posa.at(mid) + 1) >= ( diffb.at(posa.at(l)) ) &&
                stc.query(posa.at(l)+1, posa.at(mid) + 1) >= ( diffc.at(posa.at(l)) ) ){
                ok = mid;
                // mid自身がこれを満たす場合は答えとする
                if(diffb.at(posa.at(mid)) >= diffb.at(posa.at(l))&&
                   diffc.at(posa.at(mid)) >= diffc.at(posa.at(l))){
                    ans = min(ans, posa[mid] - posa[l] + 1);
                }
            }
            else ng = mid;
        }
    }
    if(ans == 1e9) ans = -1;
    cout << ans << "\n";

}
```

https://codeforces.com/contest/1605/submission/135207826