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\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_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 操作应当输出的值。

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

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\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$。 所有输入值均为整数。最初，序列 $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$。

标签: AtCoder|abc342G

来源

AtCoder|abc342G