自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:18:06，当前版本为作者最后更新于2020-03-03 09:30:41，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题面传送门

原来 IOI 也有这么水的题目。

和 P1383 几乎一模一样，赶紧去水吧（

看到撤销操作，基本上就是主席树了，是一道主席树的练手题。

对于 T 操作：在原来的版本上新建一个版本。

对于 U 操作：把根换到 $x$ 次操作以前的版本。

对于 P 操作：打印当前版本上的第 $x$ 的字符，如果你的主席树区间从 $1$ 开始，就要 $x\gets x+1$。需要注意的是每次的修改不算一个指令。

然后就是很基础的实现：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,m,nd,r[N],ls[N<<5],rs[N<<5],sz[N<<5];
char val[N<<5];
void modify(int pre,int &x,int l,int r,char c){
	sz[x=++nd]=sz[pre]+1,ls[x]=ls[pre],rs[x]=rs[pre];
	if(l==r){val[x]=c; return;}
	int m=l+r>>1;
	if(sz[ls[pre]]<m-l+1)modify(ls[pre],ls[x],l,m,c);//左边还有空位，就往左边跑
	else modify(rs[pre],rs[x],m+1,r,c);
}
char query(int id,int l,int r,int pos){
	if(l==r)return val[id];
	int m=l+r>>1;
	if(pos<=sz[ls[id]])return query(ls[id],l,m,pos);
	else return query(rs[id],m+1,r,pos-sz[ls[id]]);
}
int main(){
	cin>>n,m=n;
	for(int i=1;i<=m;i++){
		char s,x; int p; cin>>s;
		if(s=='T')cin>>x,modify(r[i-1],r[i],1,n,x);
		if(s=='U')cin>>p,r[i]=r[i-p-1];
		if(s=='P')cin>>p,i--,m--,cout<<query(r[i],1,n,p+1)<<'\n';
	}
	return 0;
}

求赞 awa。