题目简述
$f(s)$函数为在该子串$s$中仅出现1次的字符的总数
求各个子串$f$函数的和
思路
开始考虑了前缀、后缀贡献和的做法甚至想过存储字符最后一次出现的位置
结果发现都不满足条件 (难受)
所以再考虑每个字符对答案的贡献
假设在ABCDBEFBA
中求第二个B
对答案的贡献
那么其对答案的贡献只会在字符串CDBEF
及其子串中
通过考虑子串头尾的选法可以间接得出符合条件的子串个数
可以选’C’, ‘D’, ‘B’作为子串头, 选’B’, ‘E’, ‘F’作为子串尾
因此符合条件的子串有3 * 3 = 9
种
设idx[i][j]表示字符'a' + i
在整个字符串中第j次出现的下标
则该字符对答案的贡献为1ll * (idx[i][j] - idx[i][j - 1]) * (idx[i][j + 1] - idx[i][j])
记得long long~~~
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, M = 26;
char s[N];
int len;
long long ans;
vector<int>idx[M];
int main()
{
cin >> s + 1;
len = strlen(s + 1);//字符串下标从1开始
for (int i = 0; i < M; ++i) idx[i].push_back(0);//边界处理
for (int i = 1; i <= len; ++i) idx[s[i] - 'a'].push_back(i);
for (int i = 0; i < M; ++i) idx[i].push_back(len + 1);//边界处理
for (int i = 0 ; i < M; ++i)
for (int j = 1; j < idx[i].size() - 1; ++j)
ans += 1ll * (idx[i][j] - idx[i][j - 1]) * (idx[i][j + 1] - idx[i][j]);
cout << ans;
return 0;
}