← 返回题目列表

AtCoder · tessoku_book_bf

A58. RMQ(范围最大查询)

中文机器翻译题面 查看原题

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