A1135 [CSP-S 2023] 消消乐

#include <bits/stdc++.h>
using namespace std;

// CSP-S 2023 消消乐（A1135）
//
// 思路：用栈模拟「消除相邻相同字符」，得到每个前缀消除后的剩余串（称作状态）。
// 子串 s[l..r] 可消除 <=> state(l-1) == state(r)。
// 于是只需统计「相同状态的前缀对数」。
//
// 状态用一棵 trie 精确表示：根 = 空串，每条从根出发的路径就是一个剩余串；
// 压入字符 = 走向对应孩子，弹出 = 回到父节点。没有哈希碰撞。
struct Node {
    int parent;      // 父状态 id
    int firstChild;  // 第一个孩子
    int nextSibling; // 下一个兄弟
    long long cnt;   // 该状态作为前缀状态出现的次数
    char ch;         // 从父状态走到本状态时压入的字符
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    string s;
    cin >> s;

    vector<Node> t;
    t.reserve(n + 2);
    t.push_back({-1, -1, -1, 0, 0}); // 0 号节点 = 空串状态（根）

    vector<int> path; // 栈：保存一路走过的状态 id
    path.reserve(n);
    int cur = 0;       // 当前状态（= 栈里剩下的字符拼成的串）
    long long ans = 0;

    // 每遇到一个和 cur 相同的前缀状态，就多出一个可消除子串。
    auto countState = [&](int id) {
        ans += t[id].cnt;
        t[id].cnt++;
    };

    countState(cur); // 空前缀（第 0 个字符之前）也算一个状态

    for (int i = 0; i < n; i++) {
        char c = s[i];
        if (!path.empty() && t[cur].ch == c) {
            // 栈顶字符与当前字符相同 -> 两者消除，弹栈回到父状态
            cur = path.back();
            path.pop_back();
        } else {
            // 找 cur 的、字符为 c 的孩子；没有就新建一个状态
            int child = t[cur].firstChild;
            while (child != -1 && t[child].ch != c) {
                child = t[child].nextSibling;
            }
            if (child == -1) {
                child = (int)t.size();
                t.push_back({cur, -1, t[cur].firstChild, 0, c});
                t[cur].firstChild = child;
            }
            path.push_back(cur);
            cur = child;
        }
        countState(cur);
    }

    cout << ans << "\n";
    return 0;
}