P12720 [Algo Beat Contest 002 G] Game Time

| Problem | Score | Idea | Std | Data | Check | Solution | | :----------------------------------: | :---: | :---------------------------------------------------: | :---------------------------------------------------: | :---------------------------------------------: | :-------------------------------------------------: | :----------------------------------------------------------: | | $\text{G - Game Time}$ | $600$ | [DHeasy](https://www.luogu.com.cn/user/528325) | [DHeasy](https://www.luogu.com.cn/user/528325) | [DHeasy](https://www.luogu.com.cn/user/528325) | [zhoumurui](https://www.luogu.com.cn/user/305928) | [Link](https://www.luogu.com.cn/article/36j9d1sb) by [DHeasy](https://www.luogu.com.cn/user/528325)|

小 D 和小 H 有一个长度为 $n$ 的数列 $\{a_1,a_2,\cdots a_n\}$（$a_i\in\{0,1\}$），他们想用一个子数组 $\{a_l,a_{l+1},\cdots a_r\}$ 进行游戏。 对于一个在子数组 $\{a_l,a_{l+1},\cdots a_r\}$ 上进行的游戏，过程如下：小 D 先手，两人会依次对所有 $i$ 满足 $l\le i\le r$，决定是否保留 $a_i$。**例如小 D 决定是否保留 $a_l$，小 H 决定是否保留 $a_{l+1}$，小 D 决定是否保留 $a_{l+2}$，以此类推**。最后，两人计算所有保留下来的 $a_i$ 的和，如果为偶数，则小 D 赢，如果为奇数，则小 H 赢。 现在小 D 和小 H 对于数列 $\{a_1,a_2,\cdots a_n\}$ 所有子数组 $\{a_l,a_{l+1},\cdots a_r\}$ （$1\le l\le r\le n$）进行游戏，小 D 有个问题，如果两人足够聪明，自己能赢多少次。 为了不让这个游戏变得枯燥，两人会对这个数列进行 $m$ 次区间反转。具体的，如果对区间 $[l,r]$ 进行反转操作，则对于所有满足 $l\le i\le r$ 的 $i$，如果 $a_i=1$，则将 $a_i$ 改为 $0$，否则如果 $a_i=0$，则将 $a_i$ 改为 $1$。 请你在每次修改后回答小 D 的问题。

第一行输入两个正整数 $n,m$ 表示数列长度和修改次数。 第二行输入 $n$ 个只包含 $0,1$ 的整数表示 $a_1,a_2,\cdots a_n$。 接下来 $m$ 行，每行输入两个整数 $l,r$，表示对区间 $[l,r]$ 做一次反转操作。

输出共 $m$ 行，对每次修改后单独输出一行一个整数表示小 D 问题的答案。

**【数据范围】** - $1\le n,m\le 2\times 10^5$。 - $1\le l\le r\le n$。 - $a_i\in\{0,1\}$（$1\le i\le n$）。