P17715 [HexOI Round 1] 交朋友 / friends

题目来源：【HT-130-Div.3】核桃 CSP-J 组模拟赛 [HexOI](https://www.luogu.com.cn/team/85094) 欢迎您。

小 Hex 的班上正在开展一项游戏！ 班上有 $n$ 个小朋友围成一圈，其中小 Hex 的编号为 $1$。从小 Hex 开始，小朋友们按顺时针被编号为 $1,2,3,\dots,n$。第 $i$ 个小朋友的左边是第 $i-1$ 号小朋友，右边是第 $i+1$ 号小朋友。特别地，第 $n$ 号小朋友的右边是第 $1$ 号小朋友，第 $1$ 号小朋友的左边是第 $n$ 号小朋友。 由于小朋友们都学习了编程，他们只喜欢 $0$ 和 $1$ 两个数字中的恰好一个数字。初始时，第 $i$ 位小朋友最喜欢的数字为 $a_i$。 小朋友们想交朋友。每一位小朋友都想和他**左右相邻**的两个小朋友交朋友。朋友之间要有相同的喜好，因此两位小朋友会交朋友当且仅当他们喜欢的数字**相同**。 现在老师会执行 $m$ 次操作，每次操作会改变一些小朋友喜欢的数字。具体地，第 $i$ 次操作会让 $[l_i,r_i]$ 范围内的**所有**小朋友喜欢的数字取反$^\dag$。每次操作完后，小朋友们会重新建立朋友关系。 小 Hex 想知道，每一次操作过后，班上共有几对好朋友？ $^\dag$：取反，即 $1$ 变成 $0$，$0$ 变成 $1$。

输入的第一行包含两个正整数 $n,m$，分别表示班级人数和修改次数。 输入的第二行包含 $n$ 个整数，第 $i$ 个数表示 $a_i$。 输入的第 $i+2\ (1\leq i \leq m)$ 行包含两个正整数 $l_i,r_i$，表示修改的起点和终点。

输出的第 $i\ (1\leq i\leq m)$ 行包含一个非负整数，表示在第 $i$ 次修改后班上好朋友的对数。

#### 【样例 1 解释】 初始序列为 $1,0,0,0$。 **第 1 次修改**：将编号为 $3$ 的小朋友喜欢的数字取反。 - 新序列：$1,0,\red{1},0$。 - 好朋友对：无，答案为 $0$。详细的解释如下： - 对于第 $1$ 号和第 $2$ 号小朋友，他们喜欢的数字不同（$1$ 和 $0$），因此他们不是好朋友； - 对于第 $2$ 号和第 $3$ 号小朋友，他们喜欢的数字不同（$0$ 和 $1$），因此他们不是好朋友； - 对于第 $3$ 号和第 $4$ 号小朋友，他们喜欢的数字不同（$1$ 和 $0$），因此他们不是好朋友； - 对于第 $4$ 号和第 $1$ 号小朋友，他们喜欢的数字不同（$0$ 和 $1$），因此他们不是好朋友。 **第 2 次修改**：将编号为 $1$ 至 $3$ 的小朋友喜欢的数字取反。 - 新序列：$\red{0,1,0},0$。 - 好朋友对：$(3,4),(4,1)$，答案为 $2$。详细的解释如下： - 对于第 $1$ 号和第 $2$ 号小朋友，他们喜欢的数字不同（$0$ 和 $1$），因此他们不是好朋友； - 对于第 $2$ 号和第 $3$ 号小朋友，他们喜欢的数字不同（$1$ 和 $0$），因此他们不是好朋友； - 对于第 $3$ 号和第 $4$ 号小朋友，他们喜欢的数字相同（都为 $0$），因此他们是好朋友； - 对于第 $4$ 号和第 $1$ 号小朋友，他们喜欢的数字相同（都为 $0$），因此他们是好朋友。 **第 3 次修改**：将编号为 $2$ 的小朋友喜欢的数字取反。 - 新序列：$0,\red{0},0,0$。 - 好朋友对：$(1,2),(2,3),(3,4),(4,1)$，答案为 $4$。详细的解释如下： - 对于第 $1$ 号和第 $2$ 号小朋友，他们喜欢的数字相同（都为 $0$），因此他们是好朋友； - 对于第 $2$ 号和第 $3$ 号小朋友，他们喜欢的数字相同（都为 $0$），因此他们是好朋友； - 对于第 $3$ 号和第 $4$ 号小朋友，他们喜欢的数字相同（都为 $0$），因此他们是好朋友； - 对于第 $4$ 号和第 $1$ 号小朋友，他们喜欢的数字相同（都为 $0$），因此他们是好朋友。 **第 4 次修改**，将编号为 $1$ 至 $4$ 的小朋友喜欢的数字取反。 - 新序列：$\red{1,1,1,1}$。 - 好朋友对：$(1,2),(2,3),(3,4),(4,1)$，答案为 $4$。详细的解释如下： - 对于第 $1$ 号和第 $2$ 号小朋友，他们喜欢的数字相同（都为 $1$），因此他们是好朋友； - 对于第 $2$ 号和第 $3$ 号小朋友，他们喜欢的数字相同（都为 $1$），因此他们是好朋友； - 对于第 $3$ 号和第 $4$ 号小朋友，他们喜欢的数字相同（都为 $1$），因此他们是好朋友； - 对于第 $4$ 号和第 $1$ 号小朋友，他们喜欢的数字相同（都为 $1$），因此他们是好朋友。 #### 【样例 3】 见选手目录下的 friends/friends3.in 与 friends/friends3.ans。 该样例满足测试点 $1,2$ 的约束条件。 #### 【样例 4】 见选手目录下的 friends/friends4.in 与 friends/friends4.ans。 该样例满足测试点 $3$ 的约束条件。 #### 【样例 5】 见选手目录下的 friends/friends5.in 与 friends/friends5.ans。 该样例满足测试点 $4$ 的约束条件。 #### 【样例 6】 见选手目录下的 friends/friends6.in 与 friends/friends6.ans。 该样例满足测试点 $5,6$ 的约束条件。 #### 【样例 7】 见选手目录下的 friends/friends7.in 与 friends/friends7.ans。 该样例满足测试点 $7,8$ 的约束条件。 #### 【样例 8】 见选手目录下的 friends/friends8.in 与 friends/friends8.ans。 该样例满足测试点 $9\sim 12$ 的约束条件。 #### 【样例 9】 见选手目录下的 friends/friends9.in 与 friends/friends9.ans。 该样例满足测试点 $13,14$ 的约束条件。 #### 【样例 10】 见选手目录下的 friends/friends10.in 与 friends/friends10.ans。 该样例满足测试点 $15\sim 20$ 的约束条件。 #### 【数据范围】 对于所有测试数据，保证： - $3\leq n\leq 10^5$； - $1\leq m\leq 10^5$； - 对于所有 $i(1\leq i\leq n)$，均有 $a_i=0$ 或 $a_i=1$； - 对于所有 $i(1\leq i\leq m)$，均有 $1\leq l_i\leq r_i\leq n$。 ::cute-table{tuack} |测试点编号| $n$ | $m$ | $a_i(1\leq i\leq n)$ | 特殊性质 | |:--:|:--:|:--:|:--:|:-:| |$1,2$|$\leq 10^5$|$=1$|无|无| |$3$|$\leq 10^3$|$\leq 10^3$|^|A| |$4$|^|^|^|B| |$5,6$|^|^|$=i\bmod 2$|无| |$7,8$|^|^|$=0$|^| |$9\sim 12$|^|^|无|^| |$13,14$|$\leq 10^5$|$\leq 10^5$|$=0$|^| |$15\sim 20$|^|^|无|^| 特殊性质 A：对于所有 $i(1\leq i\leq m)$，都有 $l_i=2$ 且 $r_i=n-1$。 特殊性质 B：对于所有 $i(1\leq i\leq m)$，都有 $l_i=r_i$。