G - 一点更新・区間最小値 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点: 100 点

問題文

長さ N の整数列 A = (a_0, a_1, \ldots, a_{N-1}) があります。

あなたは今からこの数列について Q 個のクエリを処理します。i 番目のクエリでは、T_i, X_i, Y_i が与えられるので、以下の処理してください。

  • T_i = 1 のとき: a_{X_i} を Y_i で置き換える
  • T_i = 2 のとき: \min \left( a_{X_i}, a_{X_i + 1}, \ldots , a_{Y_i - 1} \right) を出力する

入力

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

N Q
a_0 a_1 \cdots a_{N-1}
T_1 X_1 Y_1
\vdots
T_Q X_Q Y_Q

出力

T_i = 2 であるような各クエリについて、答えを 1 行に 1 つずつ、順に出力してください。

制約

  • 1 \leq N \leq 200{,}000
  • 1 \leq Q \leq 200{,}000
  • 1 \leq a_i \leq 10^{9}
  • T_i は 1 または 2
  • T_i = 1 ならば 0 \leq X_i < N かつ 1 \leq Y_i \leq 10^{9}

  • T_i = 2 ならば 0 \leq X_i < Y_i \leq N

入力例 

6 4
1 6 3 7 2 5
2 1 5
1 4 8
2 1 5
2 3 6

出力例 

2
3
5

  • 1 個目のクエリでは、\min(a_1, a_2, a_3, a_4) = \min(6, 3, 7, 2) = 2 を出力します。
  • 2 個目のクエリでは、a_4 が 8 に書き換えられ、A = (1, 6, 3, 7, 8, 5) という数列に変化します。
  • 3 個目のクエリでは、\min(a_1, a_2, a_3, a_4) = \min(6, 3, 7, 8) = 3 を出力します。
  • 4 個目のクエリでは、\min(a_3, a_4, a_5) = \min(7, 8, 5) = 5 を出力します。