可撤销的区间取最大值

题目描述

给定长度为 $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$ 的当前值。

输入格式

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

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

这里,$\operatorname{query}_k\ (1\le k\le 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\le i\le q)$ 应输出第 $i$ 次给出的 3 类操作应输出的值。

样例

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

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

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

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

数据范围

• $1\le N\le 2\times 10^5$
• $1\le A_i\le 10^9\ (1\le i\le N)$
• $1\le Q\le 2\times 10^5$
• 在 1 类操作中,$1\le l\le r\le N$ 且 $1\le x\le 10^9$。
• 在 2 类操作中,$i$ 不超过之前给出的操作数,且 $1\le i$。
• 在 2 类操作中,第 $i$ 个操作是 1 类操作。
• 在 2 类操作中,同一个 $i$ 不会出现多次。
• 在 3 类操作中,$1\le i\le N$。
• 所有输入值均为整数。