我的做法：只需求出从任意一个点 $i$ 开始走到哪会第一次全消完，记为 $nxt_i$。

在暴力模拟栈求出 $nxt_i$ 的过程中，还可以顺便把这个过程中所有入栈操作的点的 $nxt$ 求出来。于是，就可以从 $1$ 开始扫到 $n$，每遇到一个没有求出 $nxt$ 的点就用栈模拟一遍。

但是这样时间复杂度不对，于是加入了优化：模拟栈的时候，若某个点 $j$ 的操作为入栈，并且 $nxt_j$ 之前已经求出，那么跳过 $[j,nxt_j]$ 这一段。

我认为这样做的时间复杂度是 $O(26n)$ 的（并且通过了洛谷、核桃、云斗上的数据），但是不会证明。希望大佬能来帮忙看看。

代码如下：

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
const int maxn=2000005;
int n,nxt[maxn],st[maxn],bl[maxn],top;
char str[maxn];
long long ans;
void ct(int x){
    top=0;
    for(;x<=n;++x){
        if(top&&str[st[top]]==str[x]){
            nxt[st[top]]=x;
            top--;
        }
        else{
            if(nxt[x]!=-1){
                if(nxt[x]==0)break;
                x=nxt[x];
                continue;
            }
            st[++top]=x;
        }
        if(top==0)break;
    }
    for(int i=1;i<=top;++i)nxt[st[i]]=0;
}
signed main(){
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    n=read();
    scanf("%s",str+1);
    for(int i=1;i<=n;++i)nxt[i]=-1;
    for(int i=1;i<=n;++i)if(nxt[i]==-1)ct(i);
    for(int i=1;i<=n;++i)if(!bl[i]){
        int tmp=0;
        for(int j=i;j<=n;){
            bl[j]=1;
            j=nxt[j];
            if(!j)break;
            ++tmp;
            ++j;
        }
        //printf("%d %d\n",i,tmp);
        ans+=(long long)tmp*(tmp+1)/2;
    }
    printf("%lld",ans);
    return 0;
}