範囲最小-最大クエリ
配列に含まれる n 個の要素と q 個のクエリが与えられます。クエリには以下の 2 種類があります:
- 指定された範囲の最小値と最大値を取得するクエリ
- 配列中の特定の位置を更新するクエリ
これらのクエリを効率よく処理することが目的です。
入力
最初の行には、配列の要素数 n とクエリの数 q (1 ≤ n, q ≤ 100 000) が与えられます。
次の行には、n 個の整数 ( ) が空白区切りで与えられ、これは配列の初期要素です。
続く q 行には、クエリの種類によって以下の情報が与えられます:
- 範囲の最小値・最大値を求めるクエリ: 行の先頭に
1があり、続いて と ( ) が与えられます。これは、範囲[ $$l_i, r_i$$ ]の最小値と最大値を求めるものです。
- 配列要素の更新クエリ: 行の先頭に
2があり、続いて と ( ) が与えられます。これは、配列の 番目の要素を新しい値 に変更するものです。
出力
範囲の最小値・最大値を求めるクエリが与えられるたびに、その範囲内の最小値と最大値をそれぞれ新しい行に出力してください。
例
入力 | 出力 |
6 4
12 8 16 24 36 48
1 2 5
2 4 10
1 1 6
1 3 6 | 8 36
8 48
10 48 |
Constraints
Time limit: 0.9 seconds
Memory limit: 512 MB
Output limit: 1 MB