AcWing 2868. 子串分值
原题链接
中等
作者:
AspirinZ
,
2024-04-11 23:07:04
,
所有人可见
,
阅读 1
#include<iostream>
#include<cstring>
using namespace std;
int last[30];
const int N = 100010;
int l[N],r[N];
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
string s;
cin >> s;
int n = s.size();
for(int i = 1;i <= n;i ++)
{
l[i] = last[s[i - 1] - 'a'];
last[s[i - 1] - 'a'] = i;
}
for(int i = 0;i < 30;i ++)last[i] = n + 1;
for(int i = n;i >= 1;i --)
{
r[i] = last[s[i - 1] - 'a'];
last[s[i - 1] - 'a'] = i;
}
long long res = 0;
for(int i = 1;i <= n;i ++)
{
res += 1LL * (i - l[i]) * (r[i] - i);
}
cout << res << '\n';
return 0;
}