You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

挖战壕

题目描述

给定一个长为 $N$ 的 01 序列和 $Q$ 次操作，每次操作为以下操作的一种：

操作1：将序列的第 $l$ 个元素取反；

操作2：询问第 $l$ 个到第 $r$ 个元素之间，最长的连续的全 1 序列的长度。

输入格式

第一行有两个整数，分别表示序列的长度 $N$ 和操作的次数 $Q$。

第二行一个长为 $N$ 的字符串，保证里面只有0和1。

接下来 $Q$ 行，每行三个整数表示一次操作，格式如下：

1 l：表示操作1，即对第 $l$ 个元素取反；

2 l r：表示操作2，即查询 $[l,r]$ 内最长的连续的全 1 序列的长度。

输出格式

对于每次询问操作，输出一行一个整数表示询问的答案。

样例 #1

样例输入 #1

6 2
010011
1 3
2 2 4

样例输出 #1

2

样例 #2

样例输入 #2

6 7
010101
1 3 
2 1 4
1 4 
2 1 4
1 4
1 5
2 1 6 

样例输出 #2

3
2
5

提示

数据规模与约定

对于全部的测试点，保证 $1 \leq n, q \leq 3 \times 10^5$，$1 \leq l_i\leq r_i \leq n$。