G - Retroactive Range Chmax Editorial /

Time Limit: 5 sec / Memory Limit: 1024 MB

配点 : 625 点

問題文

長さ N の整数列 A=(A _ 1,A _ 2,\ldots,A _ N) が与えられます。

Q 個の操作を順に処理してください。 操作は次の 3 種類のいずれかです。

  • タイプ 1 の操作は整数の 3 つ組 (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 の値を出力することに対応する。

制約

  • 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 回目の操作を表し、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) にはタイプ 3 の操作のうち i 番目に入力されたもので出力すべき値を出力せよ。

入力例 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 は (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 をそれぞれ出力してください。

入力例 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

Score: 625 points

Problem Statement

You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N.

Process Q operations in order. There are three types of operations:

  • A type-1 operation is represented by a triple of integers (l,r,x), which corresponds to replacing A_i with \max\lbrace A_i,x\rbrace for each i=l,l+1,\ldots,r.
  • A type-2 operation is represented by an integer i, which corresponds to canceling the i-th operation (it is guaranteed that the i-th operation is of type 1 and has not already been canceled). The new sequence A can be obtained by performing all type-1 operations that have not been canceled, starting from the initial state.
  • A type-3 operation is represented by an integer i, which corresponds to printing the current value of A_i.

Constraints

  • 1\leq N\leq2\times10^5
  • 1\leq A_i\leq10^9\ (1\leq i\leq N)
  • 1\leq Q\leq2\times10^5
  • In a type-1 operation, 1\leq l\leq r\leq N and 1\leq x\leq10^9.
  • In a type-2 operation, i is not greater than the number of operations given before, and 1\leq i.
  • In a type-2 operation, the i-th operation is of type 1.
  • In type-2 operations, the same i does not appear multiple times.
  • In a type-3 operation, 1\leq i\leq N.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \ldots A_N
Q
\operatorname{query}_1
\operatorname{query}_2
\vdots
\operatorname{query}_Q

Here, \operatorname{query}_k\ (1\leq k\leq Q) represents the k-th operation, and depending on the type of the k-th operation, one of the following is given.

For a type-1 operation, the following is given, meaning that the k-th operation is a type-1 operation represented by (l,r,x):

1 l r x

For a type-2 operation, the following is given, meaning that the k-th operation is a type-2 operation represented by i:

2 i

For a type-3 operation, the following is given, meaning that the k-th operation is a type-3 operation represented by i:

3 i

Output

Let q be the number of type-3 operations. Print q lines. The i-th line (1\leq i\leq q) should contain the value that should be printed for the i-th given type-3 operation.

Sample Input 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

Sample Output 1

2
1
8
4
4
8
4
9
9
2
9
9

Initially, the sequence A is (2,7,1,8,2,8).

For the 1-st, 2-nd, 3-rd operations, print the values of A_1, A_3, A_4, which are 2,1,8, respectively.

The 4-th operation replaces the values of A_1, A_2, A_3, A_4, A_5 with \max\lbrace A_i,4\rbrace. Just after this operation, A is (4,7,4,8,4,8).

For the 5-th, 6-th, 7-th operations, print the values of A_1, A_3, A_4 at this point, which are 4,4,8, respectively.

The 8-th operation replaces the values of A_3, A_4, A_5, A_6 with \max\lbrace A_i,9\rbrace. Just after this operation, A is (4,7,9,9,9,9).

For the 9-th, 10-th, 11-th operations, print the values of A_1, A_3, A_4 at this point, which are 4,9,9, respectively.

The 12-th operation cancels the 4-th operation. Just after this operation, A is (2,7,9,9,9,9).

For the 13-th, 14-th, 15-th operations, print the values of A_1, A_3, A_4 at this point, which are 2,9,9, respectively.

Sample Input 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

Sample Output 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