L - Multiple Min Query Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 6 点

注意

この問題に対する言及は、2021/7/17 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

長さ N の整数列 A=(A_1, A_2, \dots ,A_N) があります。
あなたは今からこの数列について Q 個のクエリを処理します。i 番目のクエリでは、 T_i, X_i, Y_i が与えられるので、以下の処理をしてください。

  • T_i = 1 のとき
    A_{X_i} を Y_i で置き換える。
  • T_i = 2 のとき
    A_{X_i}, \ldots ,A_{Y_i}の中での最小値を p とする。X_i \leq j \leq Y_i かつ A_j = p を満たす j を全て列挙する。

制約

  • 1 \leq N, Q \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9
  • T_i は 1 または 2
  • T_i=1 ならば、1 \leq X_i \leq N かつ 0 \leq Y_i \leq 10^9
  • T_i=2 ならば、1 \leq X_i \leq Y_i \leq N
  • 入力は全て整数
  • 列挙すべき j の個数の総和は 2 \times 10^5 を超えない

入力

入力は以下の形式で標準入力から与えられる。

N Q
A_1 A_2 \dots A_N
T_1 X_1 Y_1
T_2 X_2 Y_2
:
T_Q X_Q Y_Q

出力

ある T_i = 2 のタイプのクエリにおいて、列挙すべき値が j_1, j_2, \dots , j_M ( j_1 \lt j_2 \lt \dots \lt j_M ) であるとする。 このとき以下の形式で 1 行に出力せよ。

M j_1 j_2 \dots j_M

T_i = 2 のタイプのクエリの数を Q_2 個とする。Q_2 行出力せよ。

入力例 1

6 7
3 20 3 10 15 10
2 1 6
2 4 5
1 3 10
1 1 1000000000
2 1 6
1 5 0
2 1 6

出力例 1

2 1 3 
1 4 
3 3 4 6 
1 5

Score : 6 points

Warning

Do not make any mention of this problem until July 17, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

We have a sequence of N integers A=(A_1, A_2, \dots ,A_N).
You are to process Q queries on this sequence. In the i-th query, given T_i, X_i, and Y_i, do as follows.

  • If T_i = 1:
    Replace A_{X_i} with Y_i.
  • If T_i = 2:
    Let p be the smallest value among A_{X_i}, \ldots ,A_{Y_i}. List all indices j such that X_i \leq j \leq Y_i and A_j = p.

Constraints

  • 1 \leq N, Q \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9
  • T_i is 1 or 2.
  • 1 \leq X_i \leq N and 0 \leq Y_i \leq 10^9, if T_i=1.
  • 1 \leq X_i \leq Y_i \leq N if T_i=2.
  • All values in input are integers.
  • The total number of indices j to be listed does not exceed 2 \times 10^5.

Input

Input is given from Standard Input in the following format:

N Q
A_1 A_2 \dots A_N
T_1 X_1 Y_1
T_2 X_2 Y_2
:
T_Q X_Q Y_Q

Output

Let j_1, j_2, \dots , j_M ( j_1 \lt j_2 \lt \dots \lt j_M ) be the indices to be listed for a query with T_i = 2. Then, print a line in the following format:

M j_1 j_2 \dots j_M

You should print Q_2 such lines, where Q_2 is the number of queries with T_i = 2.

Sample Input 1

6 7
3 20 3 10 15 10
2 1 6
2 4 5
1 3 10
1 1 1000000000
2 1 6
1 5 0
2 1 6

Sample Output 1

2 1 3 
1 4 
3 3 4 6 
1 5