P12554 [UOI 2024] Queries for Subarray Beauty

我们定义一个长度为 $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 的查询，输出一个整数 —— 对应子数组的**优美值**。

在第一个示例中，对于第三个查询，数组 $[-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 完成