P15934 [TOPC 2021] Flip

假设给定一个包含 $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$。

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

- $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 完成