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\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 翻译