AcWing 2868. 子串分值
原题链接
中等
作者:
无双飞怪
,
2024-04-19 17:33:27
,
所有人可见
,
阅读 2
贡献法:
//考虑每个字符对答案的贡献
a (x x x a x x x x) a
L k R
统计左边第一次出现的位置和右边出现的位置
res=(k-L)*(R-k)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include<iostream>
using namespace std;
const int N=1e5+10;
char str[N];
int l[N],r[N];
int p[26];
int main()
{
scanf("%s",str+1);
int n=strlen(str+1);//!!!特别注意strlen里要写str+1!!!
for(int i=1;i<=n;i++)
{
int t=str[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 =str[i]-'a';
r[i]=p[t];
p[t]=i;
}
long long res=0;
for(int i=1;i<=n;i++)
{
res+=(long long) (i-l[i])*(r[i]-i);
}
cout<<res;
return 0;
}