自动搬运

查看原文

来自洛谷，原作者为

	TonviaSzt 「慢慢走，欣赏啊 ~」

搬运于2025-08-24 22:04:11，当前版本为作者最后更新于2024-11-29 20:38:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

开始时有一个编号为 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])]);
		}
	}
}