A58 - RMQ (Range Maximum Queries)
Editorial
/
Time Limit: 3 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
長さ N の数列 A = (A_1, A_2, \ldots, A_N) があり、最初はすべての要素が 0 になっています。以下の 2 種類のクエリを処理してください。
- クエリ 1:A_{\mathrm{pos}} の値を x に更新する。
- クエリ 2:A_l, A_{l+1}, \ldots, A_{r-1} の最大値を答える。
ただし、与えられるクエリの数は全部で Q 個であるとします。
制約
- 入力はすべて整数である
- 1 \leq N \leq 100000
- 1 \leq Q \leq 100000
- 1 \leq \mathrm{pos} \leq N
- 0 \leq x \leq 10^9
- 1 \leq l < r \leq N + 1
入力
入力は以下の形式で標準入力から与えられます。
N Q \mathrm{Query}_1 \mathrm{Query}_2 \vdots \mathrm{Query}_Q
i 番目のクエリ \mathrm{Query}_i では、まずクエリの種類 c_i(1 または 2)が与えられます。c_i = 1 の場合は \mathrm{pos}, x が、c_i = 2 の場合は l, r が追加で与えられます。
すなわち、各クエリは以下に示す 2 つの形式のいずれかです。
1 \mathrm{pos} x
2 l r
出力
クエリ 2 の答えを、順番に出力してください。
入力例 1
8 4 1 3 16 2 4 7 1 5 13 2 4 7
出力例 1
0 13
- はじめ、A = (0, 0, 0, 0, 0, 0, 0, 0) です。
- 1 個目のクエリでは、A_3 の値を 16 に更新します。A = (0, 0, 16, 0, 0, 0, 0, 0) となります。
- 2 個目のクエリでは、(A_4, A_5, A_6) = (0, 0, 0) の最大値 0 を出力します。
- 3 個目のクエリでは、A_5 の値を 13 に更新します。A = (0, 0, 16, 0, 13, 0, 0, 0) となります。
- 4 個目のクエリでは、(A_4, A_5, A_6) = (0, 13, 0) の最大値 13 を出力します。