P12846 [蓝桥杯 2025 国 A] 翻转硬币

给定 $n$ 个硬币的初始状态，以及 $m$ 次如下类型的操作： 1. $1 \ x \ y$: 将 $[x, y]$ 之间的硬币每隔一个翻转一个，即翻转 $x, x+2, x+4, \cdots, x+2t \ (x+2t \leq y)$； 2. $2 \ x \ y$: 将 $[x, y]$ 之间的硬币每隔两个翻转一个，即翻转 $x, x+3, x+6, \cdots, x+3t \ (x+3t \leq y)$； 3. $3 \ x \ y$: 将 $[x, y]$ 之间的硬币全部翻转； 4. $4 \ x \ y$: 查询 $[x, y]$ 之间正面朝上的硬币个数。

输入的第一行包含两个正整数 $n, m$，用一个空格分隔，分别表示硬币数和操作数。 第二行包含 $n$ 个整数 $f_1, f_2, \cdots, f_n$，相邻整数之间使用一个空格分隔，表示每个硬币的初始状态，其中 $f_i = 0$ 表示第 $i$ 个硬币为反面朝上，$f_i = 1$ 表示第 $i$ 个硬币为正面朝上。 接下来 $m$ 行，每行包含三个正整数 $a_i, x_i, y_i$，相邻整数之间使用一个空格分隔，表示一次操作。

输出若干行。对于每次查询操作（$4 \ x \ y$），输出一行包含一个整数表示该查询的答案。

**【评测用例规模与约定】** 对于 20% 的评测用例，$1 \leq n, m \leq 5000$； 对于另外 20% 的评测用例，$1 \leq n, m \leq 10^5$，且没有 $1 \ x \ y$ 类型的操作； 对于另外 20% 的评测用例，$1 \leq n, m \leq 10^5$，且没有 $2 \ x \ y$ 类型的操作； 对于所有评测用例，$1 \leq n \leq 5 \times 10^5$，$1 \leq m \leq 10^5$，$f_i \in \{0, 1\}$，$a_i \in \{1, 2, 3, 4\}$，$1 \leq x_i \leq y_i \leq n$。