Preparing NOJ # Flip

3000ms 1048576K

## Description:

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, a, \dots, a[n]]$. An alternating subarray $[a[\ell],a[\ell+1],\dots,a[r]]$ of $[a, a, \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.

## Input:

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,a,\dots,a[n]$ representing the given array $[a,a,\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\}$.

## Output:

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

## Sample Input:

3 1
1 1 0
2 1 3


## Sample Output:

4


## Sample Input:

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


## Sample Output:

16
16
21
14
12
6
4
9
10
8


Info Provider CodeForces Gym

Code GYM103373F

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 10/31/2021 14:46:05

Related

Nothing Yet