题目理解

这是 BalticOI 2015 Editor 问题的解决方案。题目要求实现一个支持多级撤销的文本编辑器，并实时输出每次操作后的编辑器状态。

代码思路解析

1. 核心数据结构：可持久化线段树

代码使用可持久化线段树来维护操作序列：

struct SegmentTree {
    struct Node {
        int ls, rs;
        int mx;
    } tr[MAXN * 32];
    int cnt;
    int rt[MAXN];
};

2. 线段树的作用

线段树存储的是每个级别对应的最近活动操作时间：

• 键：撤销级别 t (0 ≤ t ≤ n)
• 值：该级别最近的活动操作编号

3. 算法流程

对于编辑操作 (x ≥ 0)：

sgt.update(i, i - 1, 0, i);
val[i] = x;

• 在级别0插入当前操作编号 i
• 记录该操作的状态值 val[i] = x

对于撤销操作 (x < 0)：

x = -x;
int y = sgt.query(i - 1, 0, x - 1) - 1;
sgt.update(i, y, x, i);

1. 查询级别 [0, x-1] 中最近的活动操作 y
2. 回退到操作 y 的状态
3. 在级别 x 记录当前撤销操作

4. 状态查询

val[sgt.query(i, 0, 0)]

总是查询级别0的最近活动操作，该操作决定了当前编辑器状态。

算法正确性分析

为什么这样设计？

• 级别0：存储编辑操作
• 级别i：存储i级撤销操作
• 撤销操作 U_i 会查找级别 [0, i-1] 的最近活动操作
• 通过线段树的 max 操作自然找到"最近"的活动操作

可持久化的作用

每次操作创建新版本，保留历史状态，支持多级撤销的嵌套效果。

复杂度分析

• 每次操作：O(log n)
• 空间复杂度：O(n log n)（可持久化线段树）
• 总复杂度：O(n log n)

关键洞察

这个解法的精妙之处在于：

1. 将撤销级别映射为线段树的键
2. 用最大值查询找到最近活动操作
3. 通过版本回退实现撤销效果
4. 级别0始终指向当前有效编辑操作

总结

这是一个典型的数据结构模拟题，通过可持久化线段树巧妙地实现了多级撤销功能。解法体现了将复杂操作规则转化为标准数据结构问题的能力，是竞赛中高级数据结构应用的典范。