C小红的子串

直接考虑每一个位置作为左端点时对于答案的贡献，比如第对于从第位开始来说，在第L位置开始有了l个字母，第R+1位置时有了R+1个字母，则第个位置的贡献为 R-L+1。

那么我们只要知道每一个位置后面的每一种字母最早在哪里出现即可。可以使用序列自动机进行维护。

for (int i = len - 1; i >= 0; i--) {
        for (int j = 0; j < 26; j++) {
            nxt[i][j] = nxt[i + 1][j];
        }
        nxt[i][s[i] - 'a'] = i;
    }

完整代码

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define sz(x) x.size()
#define lbt(x) (x)&(-x)
#define all(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
//#define Local

using namespace std;

typedef pair<int, int> PII;
typedef double db;
const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f;
const db EPS = 1e-9;

int nxt[N][27];
void solve() {
    int n, l, r; cin >> n >> l >> r;
    string s; cin >> s;
    memset(nxt, 0x3f, sizeof nxt);
    for (int i = n - 1; i >= 0; i--) {
        for (int j = 0; j < 26; j++) {
            nxt[i][j] = nxt[i + 1][j];
        }
        nxt[i][s[i] - 'a'] = i;
    }
    int res = 0;
    for (int i = 0; i < s.size();i++) {
        vector<int>v;
        for (int j = 0;j < 26;j++) {
            v.emplace_back(nxt[i][j]);
        }
        sort(all(v));
        int L = v[l - 1], R = min(v[r] - 1, n - 1);
        if (L > n - 1) continue;
        res += (R - L + 1);
    }
    cout << res << endl;
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0);
#ifdef Local
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif
    int _ = 1;
    // cin >> _ ;
    for (; _;_--) solve();
}