题目描述

假设给定一个包含 $n$ 个元素的数组，每个元素为 $0$ 或 $1$。对于任意满足 $1 \leq \ell \leq r \leq n$ 的数对 $(\ell, r)$，$[a[\ell], a[\ell + 1], \dots, a[r]]$ 是数组 $[a[1], a[2], \dots, a[n]]$ 的一个子数组。若 $[a[\ell], a[\ell + 1], \dots, a[r]]$ 满足 $a[\ell] \neq a[\ell + 1] \neq \cdots \neq a[r]$，则称其为 $[a[1], a[2], \dots, a[n]]$ 的一个交替子数组。也就是说，子数组中的每个元素都与它在子数组中的相邻元素不同。由于交替子数组的定义只考虑子数组内部的元素，因此 $[1, 0, 1]$ 仍然是 $[1, 1, 0, 1, 1]$ 的一个交替子数组。

本题将对给定的数组应用两种类型的操作：

• $1\ \ell\ r$：对于每个 $i \in [\ell, r]$，将 $a[i]$ 改为 $1 - a[i]$。
• $2\ \ell\ r$：报告满足 $\ell \leq x \leq y \leq r$ 且子数组 $[a[x], a[x + 1], \dots, a[y]]$ 是交替子数组的数对 $(x, y)$ 的总数。

请编写一个程序来维护给定的数组。你的程序必须高效地报告这些数值。

输入格式

第一行包含两个整数 $n$ 和 $q$，分别表示给定数组的长度和操作的数量。第二行包含 $n$ 个空格分隔的数 $a[1], a[2], \dots, a[n]$，表示给定的数组 $[a[1], a[2], \dots, a[n]]$。接下来 $q$ 行，其中第 $i$ 行包含三个整数 $t_i, \ell_i, r_i$，表示第 $i$ 个操作为 $t_i\ \ell_i\ r_i$。

输出格式

对于每个第二类操作，输出一行，表示报告的数值。

3 1
1 1 0
2 1 3

4

20 20
0 0 1 0 1 0 0 1 1 1 0 1 0 0 0 1 1 1 0 0
1 1 10
2 2 7
1 3 15
2 1 9
1 4 9
2 1 13
1 13 15
2 10 20
1 1 5
2 2 10
1 15 17
2 15 18
1 1 3
2 4 6
1 15 19
2 1 6
1 15 15
2 10 17
1 1 8
2 15 19

16
16
21
14
12
6
4
9
10
8

提示

• $1 \leq n \leq 200000$
• $1 \leq q \leq 200000$
• 对于所有 $i \in \{1, 2, \dots, n\}$，有 $a[i] \in \{0, 1\}$
• 对于所有 $j \in \{1, 2, \dots, q\}$，有 $t_j \in \{1, 2\}$
• 对于所有 $j \in \{1, 2, \dots, q\}$，有 $1 \leq \ell_j \leq r_j \leq q$

翻译由 DeepSeek V3.2 完成