C1380 [SCOI2010]序列操作

内存限制:256 MB 时间限制:1000 ms

题目描述

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 \le op \le 4,0 \le a \le b$)

输出

对于每一个询问操作,输出一行,包括 $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\%$ 的数据,$1 \le n, m \le 1000$

对于 $100\%$ 的数据,$1 \le n, m \le 100000$