题解

题目分析

我们需要维护一个字符串序列，支持两种操作：

1. 在末尾添加 $x$ 个字符 $c$（保证与当前末尾字符不同）
2. 回退到第 $x$ 次操作后的状态

每次操作后，需要计算当前字符串所有前缀的「最长 border 长度」之和（即 KMP 中的 $\pi$ 函数值之和）。

关键思路

1. 问题转化

题目要求的是所有前缀的 $\pi$ 值之和，即：

其中 $\pi[i]$ 是前缀 $s[1..i]$ 的最长 border 长度。

2. 压缩表示

由于操作 1 是批量添加相同字符，我们可以用 游程编码（run-length encoding）来压缩表示字符串：

• 每个块表示为 (字符, 数量)
• 例如：aaabbb 表示为 (a,3), (b,3)

3. 回退操作的处理

回退操作构成一个树形结构：

• 每个操作是一个节点
• 操作 1 在当前节点添加子节点
• 操作 2 跳转到历史节点

我们可以通过 DFS 遍历操作树 来模拟所有操作序列。

4. KMP 算法的适配

标准 KMP 算法无法直接处理压缩表示。需要修改为：

• 在游程编码的序列上进行 KMP 匹配
• 比较两个块时：字符相同且数量匹配才算匹配成功
• 支持回退的 KMP：使用 RollbackKMP 数据结构

算法实现

1. 构建操作树

for (uint32_t i = 1; i <= n; i++) {
    if (op == '1') {
        // 添加新节点作为当前节点的子节点
        buckets[cur].push_back(Node{i, cnt, c});
        cur = i;
    } else {
        // 回退到历史节点
        cur = id[target];
    }
    id[i] = cur;
}

2. DFS 遍历计算答案

auto dfs = [&](auto self, uint32_t cur) -> void {
    if (cur) ans[cur] = sum;  // 记录当前操作的答案
    
    for (每个子操作) {
        // 保存当前状态
        auto old_sum = sum;
        
        // 更新 KMP 状态，计算新增的 π 值贡献
        if (栈非空) {
            // 在压缩序列上进行 KMP 匹配
            uint32_t searched = 0;
            uint32_t pi = kmp.query_Pi(kmp.size() - 1);
            
            while (pi) {
                if (stack[pi].m_char == c) {
                    // 计算匹配的块对答案的贡献
                    uint32_t end = min(cnt, stack[pi].real_cnt());
                    sum += 计算贡献;
                    searched = end;
                    if (searched >= cnt) break;
                }
                // KMP 跳转
                pi = kmp.query_Pi(pi - 1);
            }
            
            // 处理与第一个块的匹配
            if (c == stack[0].m_char && searched != cnt) {
                // 计算剩余部分的贡献
            }
            
            kmp.push_back({int(cnt), c});
        } else {
            // 第一个块的贡献计算
            sum += cnt * (cnt - 1) / 2;
            kmp.push_back({-int(cnt), c});
        }
        
        // 递归处理子节点
        stack.push_back({int(cnt), c});
        presum.push_back(presum.back() + cnt);
        self(self, index);
        
        // 回溯
        stack.pop_back();
        kmp.pop_back();
        presum.pop_back();
        sum = old_sum;
    }
};

3. 贡献计算原理

对于每个新添加的块 (c, cnt)，我们需要计算它对于所有新前缀的 π 值的贡献：

1. 与历史块的匹配：在 KMP 的失败链上寻找可以匹配的块
2. 部分匹配：当块的数量不完全相等时，计算部分匹配的贡献
3. 边界情况：处理与第一个块的匹配

复杂度分析

• 时间复杂度：$O(n \log n)$，其中 KMP 的均摊复杂度为 $O(1)$，但需要遍历失败链
• 空间复杂度：$O(n)$，存储操作树和 KMP 状态

关键技巧

1. 操作树建模：将回退操作转化为树形结构，通过 DFS 遍历
2. 压缩 KMP：在游程编码序列上进行 KMP 匹配
3. 贡献计算：精确计算每个新块对答案的增量贡献
4. 状态回退：使用栈结构支持 DFS 回溯时的状态恢复

总结

本题通过将线性操作序列转化为树形结构，结合压缩表示的 KMP 算法，高效解决了带回退操作的字符串匹配统计问题。关键在于理解游程编码上的 KMP 匹配原理和贡献计算方法。