[AdditionalFile5212.zip](file://AdditionalFile5212.zip?type=additional_file)

#5212. 「UOI 2024 Stage 4 Day1」子数组美丽度查询

标签: 传统 | 时间限制: 2500 ms | 内存限制: 512 MiB |

题目描述

题目译自 Ukrainian Olympiads in Informatics 2024 Stage 4 Day1 T3. Запити красот підмасивів

我们称一个长度为 $m$ 的整数数组 $b$ 的权重为其元素之和的绝对值，即 $|b_1 + b_2 + \ldots + b_m|$。

我们定义数组 $c$ 分割成若干子数组的美丽度为所有子数组权重中的最小值。形式上，数组 $c$ 分割成 $k$ 个子数组 $[c_1, \ldots, c_{p_1}], [c_{p_1+1}, \ldots, c_{p_2}], \ldots, [c_{p_{k-1}+1}, \ldots, c_{p_k}]$（其中 $1 \leq p_1 < p_2 < \ldots < p_{k-1} < p_k = n$）的美丽度为 $\min(|c_1 + \ldots + c_{p_1}|, |c_{p_1+1} + \ldots + c_{p_2}|, \ldots, |c_{p_{k-1}+1} + \ldots + c_{p_k}|)$。例如，数组 $[3, -6, 4, 5, -8]$ 分割成子数组 $[3, -6], [4], [5, -8]$ 的美丽度为 $\min(|3 + (-6)|, |4|, |5 + (-8)|) = \min(3, 4, 3) = 3$。

我们定义数组 $c$ 的美丽度为其所有可能分割方式中最大的美丽度。

给定一个长度为 $n$ 的整数数组 $a$。

你需要处理 $q$ 个查询，查询分为两种类型：

1. 计算由元素 $[a_{l}, a_{l+1}, \ldots, a_r]$ 组成的数组的美丽度，其中 $(l, r)$ 是查询参数；
2. 将元素 $a_x$ 替换为 $v$，其中 $(x, v)$ 是查询参数。

输入格式

输入的第一行包含两个整数 $n$ 和 $q$ $(1 \le n, q \le 10^6)$，分别表示数组 $a$ 的长度和查询的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(-10^9 \le a_i \le 10^9)$，表示数组 $a$ 的元素。

接下来的 $q$ 行，每行包含三个整数。第一个数字 $type_i$ $(1 \le type_i \le 2)$ 表示查询类型。第一类查询格式为 1 l r $(1 \le l \le r \le n)$，第二类查询格式为 2 x v $(1 \le x \le n, -10^9 \le v \le 10^9)$。

输出格式

对于每个第一类查询，单独输出一行一个整数，表示对应数组的美丽度。

样例 1

输入

6 4
1 -3 4 2 -5 6
1 1 6
1 2 3
1 2 5
1 1 1

输出

5
3
3
1

在第一个样例的第三个查询中，数组 $[-3, 4, 2, -5]$ 的最大美丽度在分割为 $[-3], [4, 2], [-5]$ 时达到。

样例 2

输入

5 6
1 -2 3 -4 5
1 1 4
1 2 3
2 3 -6
1 2 4
2 4 2
1 1 5

输出

2
2
12
7

在第二个样例的第一个查询中，数组 $[1, -2, 3, -4]$ 的最大美丽度在分割为 $[1, -2, 3], [-4]$ 时达到。

数据范围与提示

详细子任务附加限制及分值如下表所示：