消消乐

面对这类“子串求合法性”的问题，直觉上我们有以下几种想法：

1. 暴力枚举每个子串（$O(n^3)$）：
   • 找出所有的子串（一共有 $\frac{n(n+1)}{2}$ 个）。
   • 对每个子串用栈模拟消除，看最后能不能清空。
   • 数据范围 $n \le 2 \times 10^6$，这个方法毫无疑问会超时（TLE），因为运算量高达 $10^{12}$ 级别。
2. 区间 DP（$O(n^2)$）：
   • 定义 $dp[i][j]$ 表示子串 $S[i \dots j]$ 是否可消除。
   • 状态转移通常涉及区间分裂或两端字符相等的判断。
   • 虽然比暴力好一些，但面对 $2 \times 10^6$ 的数据，$O(n^2)$ 依然会超内存和超时。

我们需要一个复杂度能达到 $O(n)$ 的神仙解法！

正解核心：栈模拟 + 字符串哈希

这道题的妙处在于巧妙结合了消除栈和字符串哈希（Rolling Hash）。

栈规范化状态

当我们从左到右扫描字符串并把字符压入一个栈中时：

• 如果当前字符和栈顶字符相同，说明它们可以相消，直接弹出栈顶。
• 如果不同，就压入栈中。

最终，栈里剩下的字符就是当前前缀经过“极限消除”后的最简形态（等价状态）。

核心数学性质

一个非常重要的性质是：

如果两个不同的前缀 $i$ 和 $j$ ($i < j$)，它们在消解后的 “栈状态”完全一样，这就意味着：从位置 $i+1$ 到位置 $j$ 这一段字符，在整个消除过程中刚好被完美抵消并清空了！

如何快速判断栈状态是否相同？（哈希优化）

如果每次都去比对栈里存的几十万个字符，速度极慢。我们可以给栈里的字符引入多项式滚动哈希：

• 每次往栈里压入一个字符时，顺便计算并更新当前栈顶的哈希值。
• 这样，无论栈有多深，它的当前形态都可以被压缩表示为一个唯一的 unsigned long long 哈希值。

算法执行流程

1. 初始化一个哈希统计表（如 unordered_map），记录每种栈状态哈希值出现的次数。
2. 初始时，空栈的哈希值为 0，且它出现过 1 次（代表基础基准）。
3. 遍历字符串的每个字符：
   • 维护栈：能消则弹栈，不能消则压栈并更新哈希值。
   • 获取当前栈的最新哈希值。
   • 统计答案：如果这个哈希值在之前出现过 $cnt$ 次，说明这期间消掉了 $cnt$ 个合法的可消除子串，将 ans 加上 $cnt$。
   • 将当前哈希值的出现次数加 1。

参考代码

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

typedef unsigned long long ULL;

const int MAXN = 2000005;

char s[MAXN];
int stk[MAXN];      // 模拟栈，存储字符
ULL h[MAXN];        // 记录每个位置入栈后的哈希值
unordered_map<ULL, long long> cnt; // 统计每种哈希状态出现的次数

int main() {
    // 提升输入输出性能
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    cin >> (s + 1);

    long long ans = 0;
    int top = 0;

    // 初始化空串状态
    h[0] = 0;
    cnt[h[0]] = 1;

    for (int i = 1; i <= n; ++i) {
        // 如果当前字符与栈顶字符相同，说明可以消除，直接出栈
        if (top > 0 && stk[top] == s[i]) {
            top--;
        } else {
            // 否则入栈，并更新当前状态的滚动哈希值（底数取 131）
            stk[++top] = s[i];
            h[top] = h[top - 1] * 131 + s[i];
        }

        // 当前栈状态对应的哈希值
        ULL current_hash = (top == 0 ? 0 : h[top]);

        // 如果该状态在之前出现过，说明中间部分可以完全消空，累加贡献
        ans += cnt[current_hash];

        // 记录当前状态出现次数
        cnt[current_hash]++;
    }

    cout << ans << "\n";

    return 0;
}

复杂度分析

• 时间复杂度：$O(n)$。每个字符最多入栈出栈一次，哈希查找和更新均为期望 $O(1)$，完美通过 $2 \times 10^6$ 的数据范围。
• 空间复杂度：$O(n)$。用于存储栈、哈希数组以及 unordered_map 的开销。