103246: [Atcoder]ABC324 G - Generate Arrays

Problem Statement

Takahashi has a sequence of length $N$: $A=(A _ 1,A _ 2,\ldots,A _ N)$. $A$ is a permutation of $(1,2,\ldots,N)$.

He is going to perform $Q$ operations to create $1+Q$ sequences. He lets $A$ be the sequence numbered $0$, and then begins the series of operations. The $i$-th operation $(1\leq i\leq Q)$ is represented by a triple of integers $(t _ i,s _ i,x _ i)$ and corresponds to the following operation (see also the explanations in Sample Input/Output).

• When $t _ i=1$, he removes the elements following the $x _ i$-th element from the sequence numbered $s _ i$ $(0\leq s _ i\lt i)$, and creates a new sequence numbered $i$ with the removed elements, keeping their order.
• When $t _ i=2$, he removes the elements greater than $x _ i$ from the sequence numbered $s _ i$ $(0\leq s _ i\lt i)$, and creates a new sequence numbered $i$ with the removed elements, keeping their order.

For a sequence $X$ of length $L$, every element of $X$ is among "the elements following the $0$-th element." Also, for any $l$ such that $L\leq l$, no element of $X$ is among "the elements following the $l$-th element."

For $i=1,2,\ldots,Q$, find the length of the sequence numbered $i$ immediately after the $i$-th operation.

Constraints

• $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)$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$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$

Output

Print $Q$ lines. The $i$-th line $(1\leq i\leq Q)$ should contain the length of the sequence numbered $i$ immediately after the $i$-th operation.

Sample Input 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

Sample Output 1

6
4
2
3
1

Initially, Takahashi has a sequence $A=(1,8,7,4,5,6,3,2,9,10)$ of length $10$. He lets $A=(1,8,7,4,5,6,3,2,9,10)$ be the sequence numbered $0$, and then begins the series of operations.

In the first operation, he removes elements greater than $4$ from the sequence numbered $0$, namely $8,7,5,6,9,10$, and creates a new sequence numbered $1$ with these elements. After this operation, the sequences numbered $0$ and $1$ are $(1,4,3,2)$ and $(8,7,5,6,9,10)$, respectively.

In the second operation, he removes the elements following the $2$-nd element from the sequence numbered $1$, namely $5,6,9,10$, and creates a new sequence numbered $2$ with these elements. After this operation, the sequences numbered $0$, $1$, and $2$ are $(1,4,3,2)$, $(8,7)$, and $(5,6,9,10)$, respectively.

For the third and subsequent operations, the sequences numbered $0,1,2,\ldots,i$ after the $i$-th operation are as follows:

• $(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)$

The length of the sequence numbered $i$ after the $i$-th operation for $i=1,2,\ldots,5$ is $6,4,2,3,1$. Print each of these in its own line.

Sample Input 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

Sample Output 2

8
8
8
0
0

The operations may create empty sequences.

Sample Input 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

Sample Output 3

8
1
8
4
2
5
3
8
1
1

问题描述

高桥有一个长度为$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$时，他从编号为$s_i$的序列（$0\leq s_i\lt i$）中移除第$x_i$个元素后面的元素，并按照原来的顺序用这些移除的元素创建一个新的编号为$i$的序列。
• 当$t_i=2$时，他从编号为$s_i$的序列（$0\leq s_i\lt i$）中移除大于$x_i$的元素，并按照原来的顺序用这些移除的元素创建一个新的编号为$i$的序列。

对于长度为$L$的序列$X$，$X$中的每个元素都在“第$0$个元素后面”。 此外，对于任何$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

最初，高桥有一个长度为$10$的序列$A=(1,8,7,4,5,6,3,2,9,10)$。 他让$A=(1,8,7,4,5,6,3,2,9,10)$成为编号为$0$的序列，并开始一系列的操作。

在第一个操作中，他从编号为$0$的序列中移除了大于$4$的元素，即$8,7,5,6,9,10$，并用这些元素创建了一个编号为$1$的新序列。在完成此操作后，编号为$0$和$1$的序列分别为$(1,4,3,2)$和$(8,7,5,6,9,10)$。

在第二个操作中，他从编号为$1$的序列中移除了第$2$个元素后面的元素，即$5,6,9,10$，并用这些元素创建了一个编号为$2$的新序列。在完成此操作后，编号为$0$，$1$和$2$的序列分别为$(1,4,3,2)$，$(8,7)$和$(5,6,9,10)$。

对于第三个及后续操作，在第$i$个操作后编号为$0,1,2,\ldots,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=1,2,\ldots,5$，在第$i$个操作后编号为$i$的序列的长度为$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