← 返回题目列表

AtCoder · abc324_g

G. 生成数组

中文机器翻译题面 查看原题

分数: 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