Help needed in a data structure problem

Правка en3, от sourabh_jangid, 2020-07-29 00:25:05

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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский sourabh_jangid 2020-07-29 00:25:05 58 Tiny change: ' \n' -> ' \n$1$ $\geq$ $N, Q$ $\leq$ $200000$ \n'
en2 Английский sourabh_jangid 2020-07-28 23:49:26 19 Tiny change: 'e array $A[i]$ i.e $(' -> 'e array $A$ from &L& to $R$ i.e $('
en1 Английский sourabh_jangid 2020-07-28 23:47:38 1342 Initial revision (published)