P15934 [TOPC 2021] Flip

Suppose you are given an array of $n$ entries where each array entry is either $0$ or $1$. For any pair $(\ell, r)$ such that $1 \leq \ell \leq r \leq n$, $[a[\ell], a[\ell + 1], \dots, a[r]]$ is a subarray of the array $[a[1], a[2], \dots, a[n]]$. An alternating subarray $[a[\ell], a[\ell + 1], \dots, a[r]]$ of $[a[1], a[2], \dots, a[n]]$ if $a[\ell] \neq a[\ell + 1] \neq \cdots \neq a[r]$. I.e., every entry in the subarray is different from its neighbors in the subarray. Since the definition of alternating subarrays only considers the entries in the subarrays, $[1, 0, 1]$ is still an altering subarray of $[1, 1, 0, 1, 1]$. In this problem, two types of operations will be applied to the given array. - $1\ \ell\ r$: for every $i \in [\ell, r]$, change $a[i]$ into $1 - a[i]$. - $2\ \ell\ r$: report the total number of pairs $(x, y)$ such that $\ell \leq x \leq y \leq r$ and subarray $[a[x], a[x + 1], \dots, a[y]]$ is an alternating subarray. Please write a program to maintain the given array. Your program must report the numbers efficiently.

The first line contains two integers $n$ and $q$, indicating the length of the given array and the number of operations. The second line contain $n$ space separated numbers $a[1], a[2], \dots, a[n]$ representing the given array $[a[1], a[2], \dots, a[n]]$. Then $q$ lines follow, and the $i$-th of them contains 3 integers $t_i, \ell_i, r_i$ where the $i$-th operation is $t_i\ \ell_i\ r_i$.

For each operation of the second type, output the reported number on one line.

- $1 \leq n \leq 200000$ - $1 \leq q \leq 200000$ - $a[i] \in \{0, 1\}$ for all $i \in \{1, 2, \dots, n\}$. - $t_j \in \{1, 2\}$ for all $j \in \{1, 2, \dots, q\}$. - $1 \leq \ell_j \leq r_j \leq q$ for all $j \in \{1, 2, \dots, q\}$.