NC14629. ChiMu's Master
描述
ChiMu在与最后的BOSS涯决斗后，虽然获得了胜利，但是涯凭借着天启病毒的力量正在慢慢恢复，因为病毒结晶正在慢慢聚合成一个一个的小恶魔，为涯提供着能量。
可是ChiMu现在已经精疲力竭了，好在ChiMu的师傅——上决╇ф及时赶到。
现在，上决╇ф只有一个佩恩，这个佩恩的编号为1，只会技能0。对于每一个佩恩，有如下操作：
rollback ci 让编号为ci的佩恩遗忘当前学习的那个技能，回滚到上一次学习的技能。
relearn ci 让编号为ci的佩恩重新学习上一次遗忘的那个技能。
check ci 检查编号为ci的佩恩，刚刚学会的那个技能的编号并输出。
fork ci 将ci佩恩复制一个，新的佩恩的编号k，k代表第k-1次执行fork操作。
输入描述
第一行输入两个正整数n，m。（1 <= n，m <= 500000 ）代表操作的指令条数和所有技能的数目。
接下来n行指令，如描述的格式。
保证一个佩恩不会学习一个已经学会的技能。
保证所有的操作都是合法的，且所有学习的技能的编号都是1-m。
输出描述
对于每一次check操作输出一排，输出对应佩恩刚刚学会的技能。
示例1
输入:
9 10 learn 1 5 learn 1 7 rollback 1 check 1 fork 1 relearn 2 check 2 rollback 1 check 1
输出:
5 7 0
C++(clang++11) 解法, 执行用时: 131ms, 内存消耗: 6776K, 提交时间: 2021-06-12 02:40:47
#include<cstdio>
const int N=500005;
int head[N],nxt[N],lst[N],val[N],n,m,cnt,ct=1;
char s[50];
int main(){
scanf("%d%d",&n,&m);
int c,p,now;
while(n--){
scanf("%s%d",s,&c);
if(s[3]=='r'){
scanf("%d",&p);
lst[++cnt]=head[c];
nxt[head[c]]=cnt;
head[c]=cnt;
val[cnt]=p;
// printf("val[%d]=%d\n",cnt,p);
}
else if(s[3]=='l'){
now=lst[head[c]];
lst[++cnt]=lst[now];
nxt[cnt]=head[c];
val[cnt]=val[now];
head[c]=cnt;
}
else if(s[3]=='e'){
now=nxt[head[c]];
// printf("now=%d\n",now);
lst[++cnt]=head[c];
nxt[cnt]=nxt[now];
val[cnt]=val[now];
head[c]=cnt;
}
else if(s[3]=='c')
printf("%d\n",val[head[c]]);
else if(s[3]=='k'){
now=head[c];
lst[++cnt]=lst[now];
nxt[cnt]=nxt[now];
val[cnt]=val[now];
head[++ct]=cnt;
}
}
return 0;
}
/*
9 10
learn 1 5
learn 1 7
rollback 1
check 1
fork 1
relearn 2
check 2
rollback 1
check 1
*/