问题1199--时空栈

1199: 时空栈

[命题人 : ]
时间限制 : 2.000 sec  内存限制 : 256 MB

题目描述

最近,dzerzhinski刚刚学会了栈这个基础数据结构,但是他却被一道简单题难住了。
栈是一种特殊的线性表,它只能在固定的一段进行插入和删除操作。栈满足“后进先出”的性质,也就是每次出栈的元素一定是最后入栈的元素。 这道题要求实现一个栈,模拟元素的进栈和出栈和查看栈顶元素。
但是dzerzhinski的栈有时空能力,每一个操作都会首先跳转到某个时间点,然后执行这个操作,再回到当前的时间。最终状态是所有操作按照时间顺序依次执行的结果。
意识到问题的dzerzhinski发现这是一个很好的训练项目,决定让你来实现一个这样有时空能力的栈。

输入

第一行一个整数n1n2×105),表示有n个操作。
后面n行,每行表示一个操作。第一个数op表示操作类型。
op=0:入栈操作。输入三个数op, t, v,表示回到时间点t,然后整数v入栈。
op=1:出栈操作。输入两个数op, t ,表示回到时间t,栈顶元素出栈。
op=2:查询栈顶元素。输入两个数op, t,表示查询时间t时的栈顶元素。
其中所有操作的时间点t满足1t109,且都不相等,保证能够有唯一的操作顺序。所有入栈整数v满足1v109。保证任意时刻不会出现空栈时出栈操作,或者在空栈的时刻查询栈顶元素操作。

输出

对于每一个查询操作,输出一行,表示到当前为止的所有操作栈顶元素。

样例输入 Copy

8
0 2 2
2 6
2 4
0 1 1
2 7
1 5
2 3
2 8

样例输出 Copy

2
2
2
2
1

提示

部分样例解释:
查询7时刻栈顶的时候,之前在2时刻入栈2,在1时刻入栈1。按照时间顺序21之后入栈,所以结果是2
查询3时刻的时候,所有操作是2时刻入栈21时刻入栈15时刻出栈,但是5时刻的操作不会在3时刻之前产生,所以结果还是2
查询8时刻的时候,所有操作是2时刻入栈21时刻入栈15时刻出栈。按照时间顺序是1入栈,2入栈,2出栈,所以栈顶是1

来源/分类