[XJB出题] [线段树] [模拟] 掀桌子(reverse)

//(╯‵□′)╯︵┻━┻ 题目描述 Description

HeRaNO喜欢追番，他每天晚上都要看番，看到吐槽的地方，他就会掀桌子…… 一天晚上，HeRaNO又看番了。他觉得自己会掀桌子，于是他将他的桌子围成一个圈，看到一个槽点，他就会以顺时针方向将L$L$号和R$R$号（包括L$L$号和R$R$号）之间的桌子掀翻。如果这个桌子已经翻了，他就会再翻回来…… 这部番太烂了，HeRaNO掀了很多次桌子，在一旁的HSD桑看不下去了，他将HeRaNO每次掀翻桌子的区间[L,R]$[L,R]$记录了下来，准备把桌子复原，他知道最后所有桌子的情况，请求出最初桌子的情况。（0$0$-掀翻，1$1$-没掀翻）

输入 Input

第1$1$行，两个正整数n，T$n，T$。n$n$表示桌子数，T$T$表示HeRaNO掀了T$T$次桌子； 第2$2$行，n$n$个数，表示桌子的最后状态。 第3$3$~T+2$T+2$行，每行两个整数L，R$L，R$，表示掀翻桌子的区间。 为了方便读入输出，操作的第i$i$行为HeRaNO的第T−i+1$T-i+1$步操作。

输出 Output

一行n$n$个数，用空格分隔，表示最初的桌子情况。

样例输入 Sample Input

8 2 1 0 1 0 1 1 0 0 4 5 5 4

样例输出 Sample Output

0 1 0 0 1 0 1 1

样例解释 Explanation

第二次HeRaNO掀翻的是[4,5]$[4,5]$区间的桌子，HSD桑要翻回来，序列变成： 1 0 1 1 0 1 0 0$1 / 0 / 1 / 1 / 0 / 1 / 0 / 0$； 第一次HeRaNO掀翻[5,4]$[5,4]$区间的桌子，序列变成： 0 1 0 0 1 0 1 1$0 / 1 / 0 / 0 / 1/ 0/ 1/ 1$。 （此处用“[]$[]$”是不合理的……）

限制 Limits

30%$30/%$的数据：n，T≤103$n，T≤10^3$； 70%$70/%$的数据：n，T≤105$n，T≤10^5$； 100%$100/%$的数据：n，T≤106$n，T≤10^6$。 Time Limit:3s$3s$ & Memory Limit:512MB$512MB$

题解 Solution 30%$30/%$的数据：送分，暴力。 70%$70/%$的数据：线段树，完成区间修改，直接下传翻转标记即可。时间复杂度O(Tlogn)$O(Tlogn)$。 100%$100/%$的数据： 先对每个位置，如果与前一个相同，就写0$0$，不同则写1$1$； 然后一个区间修改就变成了两点修改辣！ 就相当于对L$L$位置和R+1$R+1$位置取反。 然后就可以A掉辣！ 时间复杂度O(n+T)$O(n+T)$ Code

来源 Source 感谢学哥提供问题，学姐提供解答。 原题为：n$n$个二进制位排成一个环，给定初始状态。每次操作可以翻转连续的k$k$位，问全部变成1$1$或0$0$的最小操作次数。