COCI 2014.11.29 T5 STOGOVI 题解

题目理解

我们有 $N$ 步操作，初始时有一个编号为 $0$ 的空栈。在第 $i$ 步，我们会复制一个已有的编号为 $v$ 的栈，并进行以下三种操作之一：

• 加入操作：将数字 $i$ 加入新栈的顶部
• 删除操作：将新栈顶部的数字删除
• 统计操作：统计新栈与另一个栈 $w$ 中公共的不同数字个数

新创建的栈编号为 $i$。要求对每个删除操作输出删除的数，对每个统计操作输出统计结果。

问题转化

直接模拟每个栈会超时，因为 $N \leq 300,000$，复制栈的代价太高。

约束条件的理解

• 每个栈都是通过复制已有栈得到的，形成版本树结构
• 栈的操作具有后进先出特性
• 统计操作需要高效计算两个栈的公共元素

核心思路

树模型建立

将栈的版本关系建模成树：

• 每个栈对应树中的一个节点
• 节点编号 = 栈编号
• 父指针表示"复制自"的关系
• 节点深度表示栈的大小

操作处理

1. 加入操作 a v：

   • 新节点 $i$，parent = $v$
   • depth[$i$] = depth[$v$] + 1
   • val[$i$] = $i$（压入的数字）

2. 删除操作 b v：

   • 新节点 $i$，parent = parent[$v$]
   • depth[$i$] = depth[parent[$v$]]
   • val[$i$] = val[$v$]（被删除的数字）
   • 输出 val[$v$]

3. 统计操作 c v w：

   • 新节点 $i$，parent = $v$
   • 计算 $v$ 和 $w$ 的最近公共祖先 LCA
   • 答案 = depth[$v$] + depth[$w$] - 2 × depth[LCA] + 1
   • 输出答案

LCA优化

使用二进制提升法快速求LCA：

• 预处理每个节点的 $2^k$ 级祖先
• LCA查询时间复杂度：$O(\log N)$

算法实现

数据结构

const int MAXN = 300005;
const int LOG = 20;

int par[MAXN];      // 父节点
int val[MAXN];      // 节点值
int depth[MAXN];    // 节点深度
int anc[MAXN][LOG]; // 二进制提升表

初始化

par[0] = -1;
depth[0] = 0;
val[0] = 0;

预处理二进制提升

for(int k=1; k<LOG; k++) {
    for(int i=0; i<=n; i++) {
        if(anc[i][k-1] != -1) {
            anc[i][k] = anc[anc[i][k-1]][k-1];
        }
    }
}

LCA查询

int lca(int u, int v) {
    if(depth[u] < depth[v]) swap(u, v);
    
    // 提升u到与v同一深度
    int diff = depth[u] - depth[v];
    for(int k=0; k<LOG; k++) {
        if(diff & (1<<k)) {
            u = anc[u][k];
        }
    }
    
    if(u == v) return u;
    
    // 同时提升
    for(int k=LOG-1; k>=0; k--) {
        if(anc[u][k] != anc[v][k]) {
            u = anc[u][k];
            v = anc[v][k];
        }
    }
    return anc[u][0];
}

样例分析

样例1

输入：
5
a 0
a 1  
b 2
c 2 3
b 4

输出：
2
1
2

解释：

• 步骤1：复制栈0，压入1 → 栈1: {1}
• 步骤2：复制栈1，压入2 → 栈2: {1,2}
• 步骤3：复制栈2，弹出2 → 输出2，栈3: {1}
• 步骤4：复制栈2，与栈3比较 → 公共元素{1}，输出1
• 步骤5：复制栈4，弹出2 → 输出2

样例2

输入：
11
a 0
a 1
a 2
a 3
a 2
c 4 5
a 5
a 6
c 8 7
b 8
b 8

输出：
2
2
8
8

复杂度分析

• 时间复杂度：$O(N \log N)$，主要来自LCA预处理和查询
• 空间复杂度：$O(N \log N)$，存储二进制提升表

算法标签

• 树结构 - 将栈版本关系建模成树
• 最近公共祖先(LCA) - 使用二进制提升法
• 离线处理 - 预处理所有操作
• 版本控制 - 通过父指针管理栈版本
• 二进制提升 - 快速计算任意节点的第$2^k$级祖先

总结

本题的关键在于：

1. 将栈的版本关系抽象成树结构
2. 利用LCA高效计算两个栈的公共元素个数
3. 通过二进制提升优化LCA查询

这种方法避免了显式存储每个栈，在时间和空间上都达到了最优。