题目描述

我们定义一个长度为 $m$ 的整数数组 $b$ 的权值为其元素和的绝对值，即 $|b_1+b_2+...+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$ 次查询。查询有两种类型：

• 查询由元素 $[a_{l},a_{l+1},\ldots,a_r]$ 组成的子数组的优美值，其中 $(l, r)$ 为查询参数；
• 将元素 $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 的查询格式为 "$\texttt{1 l r}$" ($1\le l\le r\le n$)，类型 2 的查询格式为 "$\texttt{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

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

提示

在第一个示例中，对于第三个查询，数组 $[-3,4,2,-5]$ 的最大优美值划分方案为 $[-3],[4,2],[-5]$。

在第二个示例中，对于第一个查询，数组 $[1,-2,3,-4]$ 的最大优美值划分方案为 $[1,-2,3],[-4]$。

评分标准

• （4 分）：所有查询 $type_i = 1$；且 $a_i > 0$ 对所有 $1\le i\le n$ 成立；
• （14 分）：所有查询 $type_i = 1$；且 $n,q \le 1000$；
• （10 分）：所有查询 $type_i = 1$；且 $n,q \le 2 \cdot 10^5$，每个查询存在不超过 2 个子数组的最优划分；
• （10 分）：所有查询 $type_i = 1$；且 $q \le n \le 2 \cdot 10^5$，$l_i = 1$，$r_i = i$ 对所有 $1\le i\le q$ 成立；
• （11 分）：所有查询 $type_i = 1$；且 $n,q \le 2 \cdot 10^5$，$-5 \le \sum\limits_{j=1}^{i} a_j \le 5$ 对所有 $1\le i\le n$ 成立；
• （18 分）：所有查询 $type_i = 1$；且 $n,q \le 2 \cdot 10^5$；
• （9 分）：所有查询 $type_i = 1$；
• （16 分）：$n,q \le 2 \cdot 10^5$；
• （8 分）：无额外限制。

翻译由 DeepSeek V3 完成