AcWing 2868. 子串分值（贡献法）

AcWing 2868. 子串分值

原题链接：https://www.acwing.com/problem/content/2871/

具体分析过程如下图：

直接遍历的话太麻烦，且时间复杂度太高，所以另寻他路
字符串中只有小写字母26个，所以可以从此着手，考虑每个字母对答案的贡献度
那么枚举仅包含一个i的区间的左右端点

在这里插入图片描述

代码如下：

#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
char s[N];
//p[t]代表t字符当前所指向的位置 t -> [0, 25]
int l[N], r[N], p[26];  //l[]i, r[i]代表位置i的字符的前后一次出现的位置
int main() {
    scanf("%s", s + 1); //[1, n]
    int n = strlen(s + 1);
    //给左区间赋值
    for(int i = 0; i < 26; i++ )   p[i] = 0;      //将第0个位置设为i字符左极值
    for(int i = 1; i <= n; i++ ) {
        l[i] = p[s[i] - 'a'];   //i位置的t字符上次出现位置给l[i]
        p[s[i] - 'a'] = i;  //存下t字符此次出现的位置i，以方便下次赋值给l[]
    }  
    //给右区间赋值
    for(int i = 0; i < 26; i++ )    p[i] = n + 1;  //当前指向n+1位置，也就是在n+1位置设置哨兵
    for(int i = n; i >= 1; i--) {
        r[i] = p[s[i] - 'a'];
        p[s[i] - 'a'] = i;  //存下t字符此次出现的位置i，以方便赋值给r[]
    }
    LL res = 0;
    for(int i = 1; i <= n; i++) {
        res += (LL)(i - l[i]) * (r[i] - i);
    }
    cout << res;
    return 0;
}