思路与算法

把消去相邻相同字符看成栈约简；用Trie节点精确表示每个不同约简栈，遇到栈顶相同则退父，否则沿该字符子节点压入。统计每个前缀到达的节点次数，同节点的两前缀组成一个可消除子串。

正确性说明

规则cc消空可用标准栈得到唯一约简串；等价地字符各自为自身逆元，前缀P_j=P_i*子串，所以子串约简为空当且仅当两前缀约简状态相同。Trie共享相同栈内容，退父和压子精确实现这个状态，不用概率哈希。每次加入当前状态此前出现次数，恰计全部左端点且不计空子串。

复杂度

O(26n)时间、O(n)空间，字符集固定26；稀疏子边链至多扫描26条，含节点数组预留和初始空前缀频次1。

易错点

答案用64位，n=2000000时可超32位。不能只数相邻相等字符，也不能用单个栈深度代替完整栈内容；节点复用必须按父节点与字符共同区分。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct DS {
    vector<int> p, s;
    DS(int n) : p(n), s(n, 1) {
        iota(p.begin(), p.end(), 0);
    }
    int find(int u) {
        while (p[u] != u) {
            p[u] = p[p[u]];
            u = p[u];
        }
        return u;
    }
    bool join(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b)
            return false;
        if (s[a] > s[b])
            swap(a, b);
        p[a] = b;
        s[b] += s[a];
        return true;
    }
};

int main() {
    int n;
    string s;
    cin >> n >> s;
    vector<int> par(1, -1), ch(1, -1), head(1, -1), next(1, -1);
    vector<long long> count(1, 1);
    par.reserve(n + 1);
    ch.reserve(n + 1);
    head.reserve(n + 1);
    next.reserve(n + 1);
    count.reserve(n + 1);
    int state = 0;
    long long ans = 0;
    for (char c : s) {
        int a = c - 'a';
        if (ch[state] == a)
            state = par[state];
        else {
            int v = head[state];
            while (v >= 0 && ch[v] != a)
                v = next[v];
            if (v < 0) {
                v = par.size();
                par.push_back(state);
                ch.push_back(a);
                next.push_back(head[state]);
                head.push_back(-1);
                count.push_back(0);
                head[state] = v;
            }
            state = v;
        }
        ans += count[state]++;
    }
    cout << ans << "\n";
}