P12547 [UOI 2025] Simple Subsequence

我们称一个整数数组 $d_1, d_2, \ldots, d_m$ 为*好的*，如果其长度为 $0$，或者对于任意 $1 \le i \le m$，$\sum\limits_{j=1}^{i} d_j$ 和 $\sum\limits_{j=i}^{m} d_j$ 都非负。其中 $\sum\limits_{j=l}^{r} d_j$ 表示 $d_l + d_{l+1} + \ldots + d_r$。 我们定义数组的 **美丽值** 为其最长 **好的** 子序列$^1$的长度。 给定一个长度为 $n$ 的数组 $a$，其元素**仅由 $-1$ 和 $1$ 组成**。 你需要处理 $q$ 个查询，查询分为两种类型： - 将元素 $a_p$ 替换为 $-a_p$，其中 $p$ 为查询参数； - 查询由元素 $[a_{l}, a_{l+1}, \ldots, a_r]$ 组成的数组的 **美丽值**，其中 $(l, r)$ 为查询参数。

第一行包含两个整数 $n$, $q$ $(1 \le n, q \le 5 \cdot 10^5)$ —— 数组 $a$ 的长度和查询的数量。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(a_i \in \{-1, 1\})$ —— 数组 $a$ 的元素。 接下来的 $q$ 行描述查询。第一个数字 $type_i$ $(1 \le type_i \le 2)$ 表示查询类型。类型为 $1$ 的查询格式为 $\texttt{1 p}$ $(1 \le p \le n)$，类型为 $2$ 的查询格式为 $\texttt{2 l r}$ $(1 \le l \le r \le n)$。

对于每个类型为 $2$ 的查询，输出一行一个整数 —— 对应数组的*美丽值*。

$^1$ 数组 $c$ 称为数组 $b$ 的子序列，如果可以通过从 $b$ 中删除若干元素（可能为零）得到 $c$。空数组是任何数组的子序列。 ### 评分标准 - （$2$ 分）：对于所有 $1 \le i \le n$，$a_i = (-1)^{i+1}$，且没有类型 $1$ 的查询； - （$7$ 分）：$n \le 16$，且没有类型 $1$ 的查询； - （$21$ 分）：$n, q \le 100$； - （$20$ 分）：$n, q \le 3000$； - （$27$ 分）：$n, q \leq 2 \cdot 10^5$，且没有类型 $1$ 的查询； - （$14$ 分）：$n, q \leq 2 \cdot 10^5$； - （$9$ 分）：无额外限制。 翻译由 DeepSeek V3 完成