#854. [SCOI2010] 序列操作

[SCOI2010] 序列操作

[SCOI2010] 序列操作

题目描述

lxhgww 最近收到了一个 0101 序列,序列里面包含了 nn 个数,下标从 00 开始。这些数要么是 00,要么是 11,现在对于这个序列有五种变换操作和询问操作:

  • 0 l r[l,r][l, r] 区间内的所有数全变成 00
  • 1 l r[l,r][l, r] 区间内的所有数全变成 11
  • 2 l r[l,r][l,r] 区间内的所有数全部取反,也就是说把所有的 00 变成 11,把所有的 11 变成 00
  • 3 l r 询问 [l,r][l, r] 区间内总共有多少个 11
  • 4 l r 询问 [l,r][l, r] 区间内最多有多少个连续的 11

对于每一种询问操作,lxhgww 都需要给出回答,聪明的程序员们,你们能帮助他吗?

输入格式

第一行两个正整数 n,mn,m,表示序列长度与操作个数。 第二行包括 nn 个数,表示序列的初始状态。 接下来 mm 行,每行三个整数,表示一次操作。

输出格式

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

样例 #1

样例输入 #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

样例输出 #1

5
2
6
5

提示

【数据范围】 对于 30%30\% 的数据,1n,m10001\le n,m \le 1000; 对于100%100\% 的数据,1n,m1051\le n,m \le 10^5