Description
约翰得到了一台时光机，他可以用这台机器回到过去（但不能到未来），改变他家的牛群。约翰 打算依次进行 N 步操作，每步操作分为三种：
• 买入操作以 a 表示，后接一个参数 i，表示约翰新买了一头编号为 i 的奶牛，将其放入牛棚
• 卖出操作以 s 表示，表示约翰会将牛棚中最近买入的一头奶牛卖掉
• 时光倒流的操作以 t 表示，后接一个参数 k，表示约翰将发动时光机，牛棚将返回到第 k 步操 作之前的状态
请帮助约翰记录牛棚里的奶牛信息，每当执行完一步操作后，输出目前在牛棚里的最近买入的奶牛， 如果当时牛棚里没有奶牛了，输出 −1。
Input Format
第一行：单个整数 N ，1 ≤ N ≤ 80000
• 第二行到 N + 1 行：每行代表一步操作，开头有一个小写字母
– 如果是 a，表示买入操作，后接一个参数 i，1 ≤ i ≤ 1000000
– 如果是 s，表示卖出操作
– 如果是 t，表示时光倒流的操作操作，后接一个参数 k，若这是第 i + 1 行，则 1 ≤ k ≤ i
Output Format
• 第一行到第 N 行：第 i 行有一个整数，表示在第 i 步操作后，在牛棚里最近买入的奶牛，如果 当时牛棚里没有奶牛，输出 −1
Sample Input
12 a 5 a 3 a 7 s t 2 a 2 t 4 a 4 s t 7 s s
Sample Output
5 3 7 3 5 2 7 4 7 2 5 -1
Q# Query Owned Cows Output Comments
1 a 5 -> [5] => 5 Add a new cow with ID 5
2 a 3 -> [5,3] => 3 Add a new cow with ID 3
3 a 7 -> [5,3,7] => 7 Add a new cow with ID 7
4 s -> [5,3] => 3 Sell recent cow 7
5 t 2 -> [5] => 5 Revert time to before query 2
6 a 2 -> [5,2] => 2 Add a new cow with ID 2
7 t 4 -> [5,3,7] => 7 Revert time to before query 4
8 a 4 -> [5,3,7,4] => 4 Add a new cow with ID 4
9 s -> [5,3,7] => 7 Sell recent cow 4
10 t 7 -> [5,2] => 2 Revert time to before query 7
11 s -> [5] => 5 Sell recent cow 2
12 s -> [] => -1 Sell recent cow 5
这道题如果没有t操作就是模拟出栈入栈过程，但现在却多了一个时光倒流操作，问题明显没有那么简单了。你不能记录每个时刻的操作然后真的模拟时光回溯。
但可以发现每次查询只关注栈顶元素，所以我们可以采用链表来实现时光回溯，开两个数组q[i]表示i时刻栈顶元素，s[i]表示i时刻由s[i]时刻过来的。
最后附上代码。
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
using namespace std;
int q[80001];
int s[800001];
int n;
char c[10];
int x;
int main()
{
scanf("%d",&n);
q[0]=-1;
for(int i=1;i<=n;i++)
{
scanf("%s",c);
if(c[0]=='a')
{
scanf("%d",&x);
q[i]=x;
s[i]=i-1;
}
if(c[0]=='s')
{
q[i]=q[s[i-1]];
s[i]=s[s[i-1]];
}
if(c[0]=='t')
{
scanf("%d",&x);
q[i]=q[x-1];
s[i]=s[x-1];
}
printf("%d
",q[i]);
}
}