[Scoi2010]序列操作

时间限制:10s      空间限制:64MB

题目描述

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都需要给出回答,聪明的程序员们,你们能帮助他吗?


输入格式

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


输出格式

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


样例输入

   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

样例输出

   5
   2
   6
   5


提示

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


题目来源

Day2