题解 P6166 【[IOI2012]小龙虾代书】

· · 题解

题面传送门

原来 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。