题目描述
Farmer John 买了台时光机，这使得他可以方便地管理自己的奶牛群。
他现在有 NN 个操作（1≤N≤8×1041≤N≤8×104），每次操作仅可能是如下三种之一：
a x：添加一头编号为 xx 的奶牛（1≤x≤1061≤x≤106）。s：卖掉最近添加的奶牛（保证此时至少有一头奶牛）。t x：回到第 xx 次操作前的状态（保证第 xx 次操作存在）。
你需要在 FJ 执行每次操作后输出他拥有的最新的奶牛的编号。特别地，如果没有奶牛，输出 −1−1。
输入格式
第一行一个整数 NN。
接下来 NN 行，每行描述一次操作。
输出格式
第 ii 行输出第 ii 次操作后 FJ 拥有的最新的奶牛的编号。特别地，如果没有奶牛，输出 −1−1。
样例 #1
样例输入 #1
12
a 5
a 3
a 7
s
t 2
a 2
t 4
a 4
s
t 7
s
s
Copy
样例输出 #1
5
3
7
3
5
2
7
4
7
2
5
-1
Copy
提示
下面是样例解释，其中拥有的奶牛已经按添加顺序排好。
| 操作编号 | 操作 | 拥有的奶牛 | 输出 |
|---|---|---|---|
| 1 | a 5 | 5 | |
| 2 | a 3 | 5,3 | 3 |
| 3 | a 7 | 5,3,7 | 7 |
| 4 | s | 5,3 | 3 |
| 5 | t 2 | 5 | |
| 6 | a 2 | 5,2 | 2 |
| 7 | t 4 | 5,3,7 | 7 |
| 8 | a 4 | 5,3,7,4 | 4 |
| 9 | s | 5,3,7 | 7 |
| 10 | t 7 | 5,2 | 2 |
| 11 | s | 5 | |
| 12 | / | -1 | |
#include<bits/stdc++.h>
using namespace std;
int f[80001][801],f2[80010],t,n=0,m,n2,fn[80001];
char ch;
int main(){
ios::sync_with_stdio (false);
cin>>t;
f2[0]=-1;
f[0][0]=-1;
for(int i=1;i<=t;i++){
f[i][0]=-1;
cin>>ch;
if(ch=='a'){
cin>>m;
f2[++n]=m;
}
else if(ch=='s'){
//if(n>=1){
f2[n]=0;
n--;
//}
}
else if(ch=='t'){
cin>>m;
for(int j=0;j<=fn[m-1];j++){
f2[j]=f[m-1][j];
}
n=fn[m-1];
}
n2++;
cout<<f2[n]<<"\n";
for(int j=0;j<=n;j++){
f[n2][j]=f2[j];
// cout<<f2[j]<<" ";
}
//cout<<"\n";
fn[n2]=n;
}
}