考虑预处理。 处理 $a$ 数组，每次走到一个位置 $i$，往前搜索。 当前位置不等于 $i$ 则通过这个位置继续往前查找。一直到当前位置等于 $i$，或者到达最前端则停止。 接下来进行第二次处理。 由于已经对 $a$ 进行过预处理，在计算时只需要从有值的点分别往前统计即可。 最后求一遍和。
/*
8
accabccb*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2000010;
int n, a[N], f[N],tot;
char s[N];
signed main() {
memset(a, -1, sizeof a);
cin>>n;
for(int i=1;i<=n;i++) cin>>s[i];
for(int i=1;i<=n;i++) a[i]=i-1;
for(int i=1;i<=n;i++){
while(s[a[i]]!=s[i])
{
if(a[i]==-1) break;
a[i]=a[a[i]]-1;
}
}
// for(int i=1;i<=n;i++)
// {
// cout<<a[i]<<' ';
// }
// cout<<endl;
for(int i=1;i<=n;i++) {
if(a[i]!=-1) f[i]=f[a[i]-1]+1;
}
//
// for(int i=1;i<=n;i++)
// {
// cout<<f[i]<<' ';
// }
// cout<<endl;
for(int i=1;i<=n;i++) {
tot+=f[i];
}
cout<<tot<<endl;
}