AT_abc342_g [ABC342G] Retroactive Range Chmax

题目描述

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

请依次处理 $Q$ 个操作。操作有以下三种类型之一：

• 类型 $1$ 的操作由整数三元组 $(l,r,x)$ 表示，对 $i=l,l+1,\ldots,r$，将 $A_i$ 替换为 $\max\{A_i,x\}$。
• 类型 $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\leq k\leq Q)$ 表示第 $k$ 次操作，具体格式如下：

对于类型 $1$ 的操作：

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

表示第 $k$ 次操作为 $(l,r,x)$ 的类型 $1$ 操作。

对于类型 $2$ 的操作：

$2$ $i$

表示第 $k$ 次操作为 $i$ 的类型 $2$ 操作。

对于类型 $3$ 的操作：

$3$ $i$

表示第 $k$ 次操作为 $i$ 的类型 $3$ 操作。

输出格式

设所有类型 $3$ 操作的个数为 $q$，请输出 $q$ 行。第 $i$ 行（$1\leq i\leq q$）输出第 $i$ 个被输入的类型 $3$ 操作所要求的值。

输入输出样例 #1

输入 #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

输入输出样例 #2

输入 #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

说明/提示

数据范围

• $1\leq N\leq 2\times 10^5$
• $1\leq A_i\leq 10^9\ (1\leq i\leq N)$
• $1\leq Q\leq 2\times 10^5$
• 对于类型 $1$ 操作，$1\leq l\leq r\leq N$ 且 $1\leq x\leq 10^9$
• 对于类型 $2$ 操作，$i$ 不超过此前操作次数且 $1\leq i$
• 对于类型 $2$ 操作，第 $i$ 次操作为类型 $1$
• 对于类型 $2$ 操作，$i$ 不会重复
• 对于类型 $3$ 操作，$1\leq i\leq N$
• 所有输入均为整数

样例说明 1

初始时，数列 $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\{A_i,4\}$。操作后，$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\{A_i,9\}$。操作后，$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$。

由 ChatGPT 4.1 翻译