题目描述

这题我没写出来，然后看了别人的代码半天还是不会。同宿舍的大神看不下去了就过来帮我一把。我梳理完思路后就写个题解加深记忆。
有个叫贡献值的内容我有时间再写。
ps:以下出现的i都从1开始

更新一下贡献值的计算方式
首先，贡献值的计算简单来说就是选定字母的（前边相同字母下标之差）×（后边相同字母下标之差）（取绝对值）。 我令字母a,b,a,b,c对应的下标分是1,2,3,4,5。通过观察，第一个a对应的下标为1，前边没有相同字符，所以下标之差就是1-0=1。后边有处在第三位的a，他两下标之差就是3-1=2。所以第一个a的贡献就是1×2=2。同理，b2的贡献为(2-0)(4-2)=4，a3=6，b4=4,c5=(5-0)(6-5)=5，sum=a1+b2+a3+b4+c5=21。
以下是for循环里，i从1到5时，pre[i]和nest[i]的变化过程

很奇怪，我能上传nest函数的图但上传不了pre的图，不懂为啥。不过推导方式也是同理的，但计算pre[i]的值的时候，要注意，h[i]初始值为0

样例

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
char str[N];          //str[i]代表第i个字母的位置（从1开始）
int pre[N];           //pre[i]代表第i个字母上一次出现的位置（从1开始）
int nest[N];          //nest[i]代表第i个字母下一次出现的位置（从1开始）
int h[26];           //h[i]代表a-z字母出现的下标(下标从1开始),默认h[i]的数值为0
ll sum;              
int main()
{
    cin>>str + 1;    // 从下标为1开始输入字符串
    int len=strlen(str+1);   //读取字符串长度

    for(int i=1;i<=len;i++)    //遍历字符串
    {
        int t=str[i] - 'a';   //t代表输入的字符串中第i个字符与字符a的下标之差.a-a=0、b-a=1等等
        pre[i]=h[t];          //通过h[t]数组状态的更新来给pre[i]赋值
        h[t]=i;               //更新h[t]的状态
    }
    for(int i=0;i<26;i++)h[i]=len+1;  //令h[i]的数值为len+1
    for(int i=len;i>=1;i--)
    {
        int t=str[i]-'a';
        nest[i]=h[t];                 //如果没有出现下一个同样的字母(比如c就没有下一位）,默认（c）下一次出现的位置为len+1
        h[t]=i;
    }
    for(int i=1;i<=len;i++)
    {
        sum+=(ll)(i-pre[i])*(nest[i]-i);
    }
    cout<<sum<<endl;
    return 0;
}