408902: GYM103373 F 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\le \ell \le r\le 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 alterating 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$$$.

• $$$1\le n \le 200000$$$
• $$$1\le q \le 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\le \ell_j \le r_j \le q$$$ for all $$$j\in \{1,2,\dots,q\}$$$.

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

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