P4810 [COCI2014-2015#3] STOGOVI

· · 题解

题目大意

开始时有一个编号为 0 的空栈。第 i 步选择一个栈 v，将它复制一份到栈 i 并进行以下其中一种操作：

a.将数字 i 加入新栈的顶部。

b.将新栈顶部的数字删除。

c.选择另外一个编号为 w 的栈，并统计有多少个相同的数同时存在于新栈与栈 w 中。

思路分析

一眼可持久化类的题目，但是可持久化数据结构我已经忘光了。

可持久化的题显然不能将每种状态都记录下来，可以考虑将所有状态集中到一棵树上，每个分支可以看作不同状态的延伸。这样做的好处是每次新增状态的本质就是原树节点或原树节点的简单延伸。

回归本题，使用树的方法做达到可持久化的效果：

我们维护每个栈栈顶的元素 top_i，对于 a 操作，即原树新增节点，且父亲节点为 top_v；

对于 b 操作 ，直接将 top_i 赋值为 top_v 的父节点即可；

对于c操作，先令 top_i=top_v，由于每个元素互不相同且树只会向下简单延伸的性质，两栈相同数的个数即为 top_i 与 top_w 节点的 LCA 深度，倍增维护即可。

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int n,a[N],dep[N],f[N][20];
char op[2];
inline int Rd(){
    int s=0,w=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
    return s*w;
}
int LCA(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=19;~i;i--) if(dep[f[x][i]]>=dep[y]) x=f[x][i];
    if(x==y) return x;
    for(int i=19;~i;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    return f[x][0];
}
int main(){
    freopen("stack.in","r",stdin);
    freopen("stack.out","w",stdout);
    n=Rd();
    for(int i=1;i<=n;i++){
        scanf("%s",op);
        if(*op=='a'){
            int v=Rd();
            a[i]=i;dep[i]=dep[a[v]]+1;
            f[i][0]=a[v];
            for(int j=1;j<20;j++) f[i][j]=f[f[i][j-1]][j-1];
        }else if(*op=='b'){
            int v=Rd();
            a[i]=f[a[v]][0];
            printf("%d\n",a[v]);
        }else{
            int v=Rd(),w=Rd();
            a[i]=a[v];
            printf("%d\n",dep[LCA(a[i],a[w])]);
        }
    }
}