分数: 600 点
问题陈述
Takahashi 有一个长度序列 N: A=(A _ 1,A _ 2,\ldots,A _ N). A 是一个排列 (1,2,\ldots,N).
他要表演 Q 操作创建 1+Q 序列。 他让 A 是编号的序列 0,然后开始一系列操作。 的 i第次操作 (1\leq i\leq Q) 由整数三元组表示 (t _ i,s _ i,x _ i) 并对应于以下操作(另请参阅示例输入/输出中的说明)。
- 当 t _ i=1,他删除了以下元素 x _ i- 编号序列中的第一个元素 s _ i (0\leq s _ i\lt i),并创建一个新的序列编号 i 删除元素,保持其顺序。
- 当 t _ i=2,他删除了大于的元素 x _ i 来自编号的序列 s _ i (0\leq s _ i\lt i),并创建一个新的序列编号 i 删除元素,保持其顺序。
对于序列 X 长度 L,每个元素 X 属于“以下元素” 0- 第一个元素。” 另外,对于任何 l 这样 L\leq l,没有元素 X 属于“以下元素” l- 第一个元素。”
对于 i=1,2,\ldots,Q,求编号序列的长度 i 紧接着 这 i-第次操作。
约束
- 1\leq N\leq2\times10^5
- 1\leq A _ i\leq N\ (1\leq i\leq N)
- A _ i\neq A _ j\ (1\leq i\lt j\leq N)
- 1\leq Q\leq2\times10^5
- t _ i=1,2\ (1\leq i\leq Q)
- 0\leq s _ i\lt i\ (1\leq i\leq Q)
- 0\leq x _ i\leq N\ (1\leq i\leq Q)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N A _ 1 A _ 2 \ldots A _ N Q t _ 1 s _ 1 x _ 1 t _ 2 s _ 2 x _ 2 \vdots t _ Q s _ Q x _ Q
输出
打印 Q 行。 的 i第行 (1\leq i\leq Q) 应包含编号序列的长度 i 紧随其后 i-第次操作。
样本输入 1
10 1 8 7 4 5 6 3 2 9 10 5 2 0 4 1 1 2 2 0 2 2 2 5 1 0 1
示例输出 1
6 4 2 3 1
最初,高桥有一个序列 A=(1,8,7,4,5,6,3,2,9,10) 长度 10。 他让 A=(1,8,7,4,5,6,3,2,9,10) 是编号的序列 0,然后开始一系列操作。
在第一个操作中,他删除了大于的元素 4 来自编号的序列 0,即 8,7,5,6,9,10,并创建一个新的序列编号 1 与这些元素。执行此操作后,序列编号为 0 和 1 是 (1,4,3,2) 和 (8,7,5,6,9,10)。
在第二个操作中,他删除了后面的元素 2- 编号序列中的第一个元素 1,即 5,6,9,10,并创建一个新的序列编号 2 与这些元素。执行此操作后,序列编号为 0, 1,和 2 是 (1,4,3,2), (8,7),和 (5,6,9,10)。
对于第三次及后续操作,编号为 0,1,2,\ldots,i 之后 i第次操作如下:
- (1,2),(8,7),(5,6,9,10),(4,3)
- (1,2),(8,7),(5),(4,3),(6,9,10)
- (1),(8,7),(5),(4,3),(6,9,10),(2)
编号序列的长度 i 之后 i的第次操作 i=1,2,\ldots,5 is 6,4,2,3,1。将其中每一项打印在自己的行中。
示例输入 2
8 6 7 8 4 5 1 3 2 5 2 0 0 1 1 0 2 2 0 1 3 8 2 2 3
示例输出 2
8 8 8 0 0
这些操作可能会创建空序列。
示例输入 3
30 20 6 13 11 29 30 9 10 16 5 8 25 1 19 12 18 7 2 4 27 3 22 23 24 28 21 14 26 15 17 10 1 0 22 1 0 21 2 0 15 1 0 9 1 3 6 2 3 18 1 6 2 1 0 1 2 5 20 2 7 26
示例输出 3
8 1 8 4 2 5 3 8 1 1