贡献值解法

以cabcdec为例

讨论中间的c的贡献值

含中间c的子串有

abc          

abcd

abcde

bc

bcd

bcde

c

cd

cde

假设前面的c为l,中间的c为p，后面的c为r,中间的c的贡献值就为 (p-l)*(r-p)

为了方便计算，对于每位字母，0位我们认为是最小的l，n+1位是最大的r

参考代码:

#include<bits/stdc++.h>

using namespace std;

string s;

pair<int,int> a[30];

int n;

long long sum;

int main() {

cin >> s;

s = '0' + s;

n = s.size() - 1;

for (int i = 1; i <= n; i++) {

auto find=a[s[i] - 'a'];

int l=find.first,p=find.second;

sum +=(p-l)*(i-p);

a[s[i] - 'a']={p,i};

}

for (int i = 0; i < 26; i++) {

int l=a[i].first,p=a[i].second,r=n+1;

if (p!=0) sum += (p-l)*(r-p);

}

cout << sum;

return 0;

}