ABC430-C - Truck Driver · znzryb

## 思路讲解

赛时AC的。

```cpp
            if(cnta>=A && cntb<B) {
				// ans+=(cnta-A+1)
                ans+=(*posa.find_by_order(cnta-A)-i+1);

            }

```

// ans+=(cnta-A+1)
hack数据：

```cpp
7 2 3
aabbaba


```

```
7
```

## AC代码

[https://atcoder.jp/contests/abc430/submissions/70626068](https://atcoder.jp/contests/abc430/submissions/70626068)



::: 源代码

```cpp
//  C - Truck Driver  
  
#include <bits/stdc++.h>  
  
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)  
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)  
#define debug(var) cerr << #var <<":"<<var<<"\n";  
#define cend cerr<<"\n-----------\n"  
#define fsp(x) fixed<<setprecision(x)  
#define all(vec) vec.begin(),vec.end()  
  
using namespace std;  
  
using  ll = long long;using ull = unsigned long long;  
using DB=double;using LD=long double;  
// using i128 = __int128;  
using CD=complex<double>;  
static constexpr ll MAXN=(ll)1e6+10,INF=(1ll<<61)-1;  
static constexpr ll mod=(ll)1e9+7; // 998244353;  
static constexpr double eps=1e-8;const double pi=acos(-1.0);  
  
#include <ext/pb_ds/assoc_container.hpp>  
using namespace __gnu_pbds;  
using ordered_set = tree<ll, null_type, less<>, rb_tree_tag,  
tree_order_statistics_node_update>;  
  
ll lT;  
  
void Solve(){  
    ll N,A,B;  
    cin>>N>>A>>B;  
    vector<char> S(N+5);  
    FOR(i,1,N) {  
        cin>>S[i];  
    }  
    ll cnta=0,cntb=0;  
    ll ans=0;  
    ll up=1;  
    ordered_set posa;  
    FOR(i,1,N) {  
        bool isb=false;  
        FOR(j,up,N) {  
            if(S[j]=='b') {  
                ++cntb;  
            }else {  
                posa.insert(j);  
                ++cnta;  
            }  
            if(cnta>=A && cntb<B) {  
// #ifdef LOCAL  
//                 debug(i);  
//                 debug(j);  
//                 debug((cnta-A+1));  
//  
// #endif  
                ans+=(*posa.find_by_order(cnta-A)-i+1);  
// #ifdef LOCAL  
//                 debug(*posa.find_by_order(cnta-A));  
//                 debug(*posa.begin());  
//                 debug((*posa.find_by_order(cnta-A)-i+1));  
//                 cend;  
// #endif  
            }  
            if(cntb>=B) {  
                up=j;  
                if(S[i]=='a') {  
                    posa.erase(i);  
                    --cnta;  
                }else {  
                    --cntb;  
                }  
  
                if(S[j]=='b') {  
  
                    --cntb;  
                }else {  
                    posa.erase(j);  
                    --cnta;  
                }  
                isb=true;  
                break;  
            }  
        }  
        if(!isb) {  
            up=N+1;  
        }  
  
    }  
    cout<<ans<<"\n";  
}  
  
signed main()  
{  
    ios::sync_with_stdio(false);  
    cin.tie(0);cout.tie(0);  
    // cin>>lT;  
    // while(lT--)        Solve();  
    return 0;  
}  
/*  
AC  
https://atcoder.jp/contests/abc430/submissions/70626068  
  
*/
```


:::


## 心路历程（WA，TLE，MLE……）