I encountered this problem in a contest, I was not able to solve it during the contest. ↵
The problem is as follows:- ↵
You are given an array $A$ where $A[i]$ is either $0$ or $1$ for $\forall$ $i$ $\leq$ $n$ $and$ $i$ $\geq$ $1$. ↵
There is an array $P$ defined as follows:- ↵
If $A[i] = 0$ then $,$ $P[i] = 0$. ↵
If $A[i] = 1$ then $,$ $P[i] = A[i] + P[i - 1]$ $,$ for $\forall$ $i$ $\leq$ $n$ $and$ $i$ $\geq$ $1$. ↵
Now you are given Q queries of two types:- ↵
$1$ $L$ $R$ $,$ Invert the array $A$ from $L$ to $R$ i.e $($ If $A[i] = 1$, then make $A[i] = 0$ and vice versa $)$. ↵
$2$ $L$ $R$ $,$ Output the sum of the array $P$ from index $L$ to $R$. ↵
Note in the query of type 1, the array $P$ will also change accordingly. And assume $P[0] = 0$. ↵
$1$ $\leq$ $N, Q$ $\leq$ $200000$ ↵
It will be helpful if someone can give some ideas.
The problem is as follows:- ↵
You are given an array $A$ where $A[i]$ is either $0$ or $1$ for $\forall$ $i$ $\leq$ $n$ $and$ $i$ $\geq$ $1$. ↵
There is an array $P$ defined as follows:- ↵
If $A[i] = 0$ then $,$ $P[i] = 0$. ↵
If $A[i] = 1$ then $,$ $P[i] = A[i] + P[i - 1]$ $,$ for $\forall$ $i$ $\leq$ $n$ $and$ $i$ $\geq$ $1$. ↵
Now you are given Q queries of two types:- ↵
$1$ $L$ $R$ $,$ Invert the array $A$ from $L$ to $R$ i.e $($ If $A[i] = 1$, then make $A[i] = 0$ and vice versa $)$. ↵
$2$ $L$ $R$ $,$ Output the sum of the array $P$ from index $L$ to $R$. ↵
Note in the query of type 1, the array $P$ will also change accordingly. And assume $P[0] = 0$. ↵
$1$ $\leq$ $N, Q$ $\leq$ $200000$ ↵
It will be helpful if someone can give some ideas.
