配点: 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 。