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

#5205. 「UOI 2025 Stage 4 Day1」简单子序列

标签: 传统 | 时间限制: 1500 ms | 内存限制: 256 MiB |

题目描述

题目译自 Ukrainian Olympiads in Informatics 2025 Stage 4 Day1 T4. Проста підпослідовність

我们称一个整数数组 $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}$。

我们定义一个数组的美丽度为它的最长好的子序列的长度。

给定一个长度为 $n$ 的数组 $a$，数组元素仅由 $-1$ 和 $1$ 组成。

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

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

注意：数组 $c$ 称为数组 $b$ 的子序列，如果可以通过从数组 $b$ 中删除若干元素（可能是零个），使得剩余元素组成数组 $c$。空数组是任意数组的子序列。

输入格式

输入的第一行包含两个整数 $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 p $(1 \le p \le n)$，第二类查询格式为 2 l r $(1 \le l \le r \le n)$。

输出格式

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

样例 1

输入

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

输出

5
2
3

样例 2

输入

4 4
1 1 1 -1
2 1 2
2 2 4
2 3 3
2 3 4

输出

2
2
1
1

数据范围与提示

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