103426: [Atcoder]ABC342 G - Retroactive Range Chmax

Problem Statement

You are given an integer sequence $A=(A_1,A_2,\ldots,A_N)$ of length $N$.

Process $Q$ operations in order. There are three types of operations:

• A type-1 operation is represented by a triple of integers $(l,r,x)$, which corresponds to replacing $A_i$ with $\max\lbrace A_i,x\rbrace$ for each $i=l,l+1,\ldots,r$.
• A type-2 operation is represented by an integer $i$, which corresponds to canceling the $i$-th operation (it is guaranteed that the $i$-th operation is of type 1 and has not already been canceled). The new sequence $A$ can be obtained by performing all type-1 operations that have not been canceled, starting from the initial state.
• A type-3 operation is represented by an integer $i$, which corresponds to printing the current value of $A_i$.

Constraints

• $1\leq N\leq2\times10^5$
• $1\leq A_i\leq10^9\ (1\leq i\leq N)$
• $1\leq Q\leq2\times10^5$
• In a type-1 operation, $1\leq l\leq r\leq N$ and $1\leq x\leq10^9$.
• In a type-2 operation, $i$ is not greater than the number of operations given before, and $1\leq i$.
• In a type-2 operation, the $i$-th operation is of type 1.
• In type-2 operations, the same $i$ does not appear multiple times.
• In a type-3 operation, $1\leq i\leq N$.
• 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$
$\operatorname{query}_1$
$\operatorname{query}_2$
$\vdots$
$\operatorname{query}_Q$

Here, $\operatorname{query}_k\ (1\leq k\leq Q)$ represents the $k$-th operation, and depending on the type of the $k$-th operation, one of the following is given.

For a type-1 operation, the following is given, meaning that the $k$-th operation is a type-1 operation represented by $(l,r,x)$:

$1$ $l$ $r$ $x$

For a type-2 operation, the following is given, meaning that the $k$-th operation is a type-2 operation represented by $i$:

$2$ $i$

For a type-3 operation, the following is given, meaning that the $k$-th operation is a type-3 operation represented by $i$:

$3$ $i$

Output

Let $q$ be the number of type-3 operations. Print $q$ lines. The $i$-th line $(1\leq i\leq q)$ should contain the value that should be printed for the $i$-th given type-3 operation.

Sample Input 1

6
2 7 1 8 2 8
15
3 1
3 3
3 4
1 1 5 4
3 1
3 3
3 4
1 3 6 9
3 1
3 3
3 4
2 4
3 1
3 3
3 4

Sample Output 1

2
1
8
4
4
8
4
9
9
2
9
9

Initially, the sequence $A$ is $(2,7,1,8,2,8)$.

For the $1$-st, $2$-nd, $3$-rd operations, print the values of $A_1, A_3, A_4$, which are $2,1,8$, respectively.

The $4$-th operation replaces the values of $A_1, A_2, A_3, A_4, A_5$ with $\max\lbrace A_i,4\rbrace$. Just after this operation, $A$ is $(4,7,4,8,4,8)$.

For the $5$-th, $6$-th, $7$-th operations, print the values of $A_1, A_3, A_4$ at this point, which are $4,4,8$, respectively.

The $8$-th operation replaces the values of $A_3, A_4, A_5, A_6$ with $\max\lbrace A_i,9\rbrace$. Just after this operation, $A$ is $(4,7,9,9,9,9)$.

For the $9$-th, $10$-th, $11$-th operations, print the values of $A_1, A_3, A_4$ at this point, which are $4,9,9$, respectively.

The $12$-th operation cancels the $4$-th operation. Just after this operation, $A$ is $(2,7,9,9,9,9)$.

For the $13$-th, $14$-th, $15$-th operations, print the values of $A_1, A_3, A_4$ at this point, which are $2,9,9$, respectively.

Sample Input 2

24
721 78 541 256 970 478 370 467 344 542 43 166 619 17 592 222 983 729 338 747 62 452 815 838
35
3 10
3 8
3 8
3 13
3 9
1 1 17 251
3 3
3 19
3 13
3 22
3 1
3 15
3 18
3 10
3 15
1 16 19 883
1 8 23 212
3 5
3 13
2 6
3 15
1 5 18 914
2 17
3 20
1 23 23 56
3 13
2 25
3 13
3 13
3 10
2 16
1 17 22 308
3 19
3 17
3 7

Sample Output 2

542
467
467
619
344
541
338
619
452
721
592
729
542
592
970
619
592
747
914
914
914
914
338
983
914

问题描述

你被给定一个长度为$N$的整数序列$A=(A_1,A_2,\ldots,A_N)$。

按照顺序处理$Q$个操作。有三种类型的操作：

• 类型-1操作由一个整数三元组$(l,r,x)$表示，对应于将每个$i=l,l+1,\ldots,r$处的$A_i$替换为$\max\lbrace A_i,x\rbrace$。
• 类型-2操作由一个整数$i$表示，对应于取消第$i$个操作（保证第$i$个操作是类型1且尚未被取消）。新序列$A$可以通过执行所有尚未被取消的类型-1操作从初始状态开始获得。
• 类型-3操作由一个整数$i$表示，对应于打印当前的$A_i$值。

限制条件

• $1\leq N\leq2\times10^5$
• $1\leq A_i\leq10^9\ (1\leq i\leq N)$
• $1\leq Q\leq2\times10^5$
• 对于类型-1操作，$1\leq l\leq r\leq N$且$1\leq x\leq10^9$。
• 对于类型-2操作，$i$不大于之前给出的操作数，且$1\leq i$。
• 对于类型-2操作，第$i$个操作是类型1。
• 对于类型-2操作，相同的$i$不会出现多次。
• 对于类型-3操作，$1\leq i\leq N$。
• 所有输入值都是整数。

输入

输入从标准输入以以下格式给出：

$N$
$A_1$ $A_2$ $\ldots$ $A_N$
$Q$
$\operatorname{query}_1$
$\operatorname{query}_2$
$\vdots$
$\operatorname{query}_Q$

其中，$\operatorname{query}_k\ (1\leq k\leq Q)$表示第$k$个操作，根据第$k$个操作的类型，会给出以下之一。

对于类型-1操作，给出以下内容，表示第$k$个操作是表示为$(l,r,x)$的类型-1操作：

$1$ $l$ $r$ $x$

对于类型-2操作，给出以下内容，表示第$k$个操作是表示为$i$的类型-2操作：

$2$ $i$

对于类型-3操作，给出以下内容，表示第$k$个操作是表示为$i$的类型-3操作：

$3$ $i$

输出

让$q$是类型-3操作的数量。打印$q$行。 第$i$行$(1\leq i\leq q)$应该包含应该为给定的第$i$个类型-3操作打印的值。

样例输入1

6
2 7 1 8 2 8
15
3 1
3 3
3 4
1 1 5 4
3 1
3 3
3 4
1 3 6 9
3 1
3 3
3 4
2 4
3 1
3 3
3 4

样例输出1

2
1
8
4
4
8
4
9
9
2
9
9

最初，序列$A$是$(2,7,1,8,2,8)$。

对于第1、2、3个操作，分别打印$A_1, A_3, A_4$的值，分别是$2,1,8$。

第4个操作将$A_1, A_2, A_3, A_4, A_5$的值替换为$\max\lbrace A_i,4\rbrace$。 在这一操作之后，$A$为$(4,7,4,8,4,8)$。

对于第5、6、7个操作，分别打印此时的$A_1, A_3, A_4$的值，分别是$4,4,8$。

第8个操作将$A_3, A_4, A_5, A_6$的值替换为$\max\lbrace A_i,9\rbrace$。 在这一操作之后，$A$为$(4,7,9,9,9,9)$。

对于第9、10、11个操作，分别打印此时的$A_1, A_3, A_4$的值，分别是$4,9,9$。

第12个操作取消第4个操作。 在这一操作之后，$A$为$(2,7,9,9,9,9)$。

对于第13、14、15个操作，分别打印此时的$A_1, A_3, A_4$的值，分别是$2,9,9$。

样例输入2

24
721 78 541 256 970 478 370 467 344 542 43 166 619 17 592 222 983 729 338 747 62 452 815 838
35
3 10
3 8
3 8
3 13
3 9
1 1 17 251
3 3
3 19
3 13
3 22
3 1
3 15
3 18
3 10
3 15
1 16 19 883
1 8 23 212
3 5
3 13
2 6
3 15
1 5 18 914
2 17
3 20
1 23 23 56
3 13
2 25
3 13
3 13
3 10
2 16
1 17 22 308
3 19
3 17
3 7

样例输出2

542
467
467
619
344
541
338
619
452
721
592
729
542
592
970
619
592
747
914
914
914
914
338
983
914