分数: 625 点
问题陈述
给你一个整数序列 A=(A_1,A_2,\ldots,A_N) 长度 N.
流程 Q 操作按顺序进行。操作分为三种类型:
- 类型 1 运算由整数三元组表示 (l,r,x),对应于替换 A_i 与 \max\lbrace A_i,x\rbrace 对于每个 i=l,l+1,\ldots,r.
- 类型 2 运算由整数表示 i,相当于取消 i-th 操作(保证 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-th 操作,并且取决于操作的类型 k-th 操作,给出以下操作之一。
对于类型 1 操作,给出以下内容,这意味着 k第一个操作是类型 1 操作,表示为 (l,r,x):
1 l r x
对于类型 2 操作,给出以下内容,这意味着 k第一个操作是 2 类操作,表示为 i:
2 i
对于类型 3 操作,给出以下内容,这意味着 k-th 操作是一个类型 3 操作,表示为 i:
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 is (2,7,1,8,2,8).
对于 1-st, 2-nd, 3-rd 操作,打印值 A_1, A_3, A_4,它们是 2,1,8。
的 4-th 操作替换的值 A_1, A_2, A_3, A_4, A_5 与 \max\lbrace A_i,4\rbrace。 就在这次手术之后, A is (4,7,4,8,4,8).
对于 5-th, 6-th, 7第次操作,打印以下值 A_1, A_3, A_4 此时,它们是 4,4,8。
的 8-th 操作替换的值 A_3, A_4, A_5, A_6 与 \max\lbrace A_i,9\rbrace。 就在这次手术之后, A is (4,7,9,9,9,9).
对于 9-th, 10-th, 11第次操作,打印以下值 A_1, A_3, A_4 此时,它们是 4,9,9。
的 12第一个操作取消 4-第次操作。 就在这次手术之后, A is (2,7,9,9,9,9).
对于 13-th, 14-th, 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