[Scoi2010]序列操作

Time Limit:10000MS  Memory Limit:65536K
Total Submit:38 Accepted:14
Case Time Limit:2000MS

Description

lxhgww最近收到了一个01序列，序列里面包含了n个数，这些数要么是0，要么是1，现在对于这个序列有五种变换操作和询问操作：
0 a b 把[a, b]区间内的所有数全变成0
1 a b 把[a, b]区间内的所有数全变成1
2 a b 把[a,b]区间内的所有数全部取反，也就是说把所有的0变成1，把所有的1变成0
3 a b 询问[a, b]区间内总共有多少个1
4 a b 询问[a, b]区间内最多有多少个连续的1
对于每一种询问操作，lxhgww都需要给出回答，聪明的程序员们，你们能帮助他吗？

Input

输入数据第一行包括2个数，n和m，分别表示序列的长度和操作数目
第二行包括n个数，表示序列的初始状态
接下来m行，每行3个数，op, a, b，（0<=op<=4，0<=a<=b

Output

对于每一个询问操作，输出一行，包括1个数，表示其对应的答案

Sample Input

10 10
0 0 0 1 1 0 1 0 1 1
1 0 2
3 0 5
2 2 2
4 0 4
0 3 6
2 3 7
4 2 8
1 0 5
0 5 6
3 3 9

Sample Output

5
2
6
5

Hint

对于30%的数据，1<=n, m<=1000
对于100%的数据，1<=n, m<=100000

Source

Day2
八中OJ总算好了。。我要开始做题了。。
这道题目本来我以为是简单的线段树问题，结果折腾了我一个半小时，最后我发现我对线段数打标记的理解不够透彻。。
这里的标记有3种，全变0，全变1，相反，关键是如果给一个东西打相反的标记的话，并不是什么真正的标记，而是要改变原有的标记，把全变0跟全变1互换，把相反跟无标记状态互换。。。
在代码中我为了方便把0的数据和1的数据用一个类来表示，再用一个大类表示综合的数据，这样相反只要交换两个数据就OK了。。
Code：
www.ideone.com/XDtvQ