【子串分值——贡献法】
题目
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
char s[N];
int l[N], r[N], p[N];
int main()
{
cin >> s+1;
int n = strlen(s+1);
for(int i = 1; i <= n; i++)
{
int t = s[i] - 'a';
l[i] = p[t];
p[t] = i;
}
for(int i = 0; i < 26; i++) p[i] = n+1;
for(int i = n; i >= 1; i--)
{
int t = s[i] - 'a';
r[i] = p[t];
p[t] = i;
}
ll ans = 0;
for(int i = 1; i <= n; i++)
{
ans += (ll)(i - l[i]) * (r[i] - i);
}
cout << ans;
}