Courses

數據結構

线段树

Module: 线段树

Problem

2 /4

线段树

Theory Click to read/hide

Error

Problem

Corwin 和 Blaze 准备入侵 Amber 以推翻 Erik。为此，他们需要组建一支军队。在他们所在的世界中，由于地形原因，有n个聚居地排成一排。众所周知，在第一个定居点中有 a₁ 战士，在第二个定居点中有 a₂，在i -th - a_i，在 n-th - a_n.

有时，Corwin 和 Blaze 发现 a_i 定居点的战士数量与预期不同。 Corwin 和 Blaze 问你 m 一个定居点最多可以提供多少战士。帮助他们识别它。

输入

第一行输入数字n 和m (1 <= n, m <= 100000) - 的个数结算和请求数量。

第二行包含n 数字a₁,a₂ >, ..., a_n (1 <= a_i <= 1000) - 定居点中的战士数量。< /分区 >

以下m 行包含数字t、l 和r ( 1 <= l <= r <= n), (0 <= t <= 1) - 如果 t 等于 0 那么l 和r ——查询边界。否则 l 为城市编号，r 为新信息。

印记
如果 t_i=0，则在第 i 行打印第 i 查询的答案，否则打印“-1”。