← 返回题目列表

AtCoder · abc342_g

G. 追溯范围 Chmax

中文机器翻译题面 查看原题

分数: 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