思路

一开始看到数据范围,n=1e5,那么只可以遍历一次,那么如何在一次之内算出全部贡献?细心一些可以发现对于字母来说只有26个,这便是本题的突破口,我们只需在这一次遍历内算出每个字母的贡献即可。
首先将子串分为n类—以第i号元素为结尾的子串(1<=i<=n)
a对于以第i号元素为结尾类子串的贡献
=0(第i号元素之前没出现过a)
=a出现时的位置(在第i号元素之前a只出现过一次)
=最近两次a出现过的位置之差(在第i号元素出现之前a出现两次以上)
由上知道我们所需记录的信息就是在当前第i号元素之前最近两次各元素出现的位置。
最后全部的贡献就是所有26个子母贡献相加即可。

Code

#include<iostream>
using namespace std;
const int Max = 1e6 + 5;

int b[30][2];//b[30]是26个字母,b[x][1]是x字母最近出现的位置,b[i][0]是x字母第二个最近出现的位置

int value()
{
   
	int sum = 0;
	for (int i = 1;i <= 26;i++)
	{
   
		if (b[i][0] != 0 && b[i][1] == 0)sum += b[i][0];
		else if (b[i][0] != 0 && b[i][1] != 0)sum += b[i][1] - b[i][0];
	}
	return sum;
}

int main()
{
   
	string str;cin >> str;
	str.insert(str.begin(), '#');//只是为了凑个位置令个元素位置+1
	long long ans = 0;
	for (int i = 1;i < str.size();i++)
	{
   
		int t = str[i] - 'a' + 1;
		if (b[t][0] == 0)b[t][0] = i;
		else if (b[t][0] != 0 && b[t][1] == 0)b[t][1] = i;
		else b[t][0] = b[t][1], b[t][1] = i;
		ans += value();
	}
	cout << ans;
}