範囲最大値クエリ (Range Maximum Queries)
n 個の要素からなる配列と、q 個のクエリが与えられます。クエリには以下の2種類があります。
- 指定した範囲内での最大値を取得するクエリ
- 配列の特定の位置を更新するクエリ
これらのクエリを効率的に処理するのが、あなたの課題です。
入力
最初の行には、配列の要素数 n と、クエリの数 q (1 ≤ n, q ≤ 100000) が与えられます。
続く行では、n 個の整数 ($1 ≤ a_i ≤ 10^9$) が空白区切りで与えられ、これは配列の初期状態を表します。
その後の q 行には、それぞれクエリが1つずつ書かれています。
- 範囲最大値クエリの場合: 行の先頭が
1で、続けて2つの整数 と ($1 ≤ li ≤ ri ≤ n$) が指定されます。この場合、[] の範囲における最大値を求めます。
- 配列更新クエリの場合: 行の先頭が
2で、続けて2つの整数 と ($1 ≤ pi ≤ n, 1 ≤ xi ≤ 10^9$) が指定されます。この場合、配列の 番目の要素を新しい値 に更新します。
出力
範囲最大値クエリについては、各クエリごとに、その範囲での最大値を1行ずつ出力してください。
例
入力 | 出力 |
6 4
1 4 2 7 5 3
1 1 3
2 2 9
1 2 5
1 3 6 | 4
9
7 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB