题目描述
一辆自动驾驶的出租车正在 Innopolis 的街道上行驶。该街道上有 n+1 个停车站点,它们将街道划分成了 n 条路段。每一路段都拥有一个路灯。当第 i 个路灯亮起,它将照亮连接第 i 与第 i+1 个站点的路段。否则这条路段将是黑暗的。
安全起见,出租车只能在被照亮的路段上行驶。换言之,出租车能从站点 a 出发到达站点 b (a<b) 的条件是:连接站点 a 与 a+1,a+1 与 a+2,……,b−1 与 b 的路段都被照亮。
在经过一些意外故障或修理之后,街道上的路灯可能是亮起的,也可能是熄灭的。
现在给定 0 时刻时,街道上路灯的初始状态。之后 1,2,…,q 时刻,每时刻会发生下列两种事件之一:
- toggle i:切换第 i 个路灯的状态。具体地说,若路灯原来亮起,则现在将熄灭;若路灯原来熄灭,则现在将亮起。
- query a b:出租车部门的负责人想知道,从 0 时刻起到当前时刻,有多少个时刻满足:出租车能够从站点 a 出发到达站点 b。
请你帮助出租车部门的负责人回答他们的问题。
输入格式
第一行包含两个整数 n 和 q——表示路灯的数量与时刻数。
第二行包含一个字符串 s 表示路灯的初始状态,si 为 1
表示第 i 个路灯初始时亮起;si 为 0
表示第 i 个路灯初始时熄灭。
接下来 q 行每行描述一个时刻的事件。第 i 行描述时刻 i 所发生的事件:
- toggle i:该时刻切换了第 i 个路灯的状态。
- query a b:计算从 0 时刻起到该时刻,共有多少个时刻满足:出租车能从站点 a 出发到达站点 b。
至少有一个时刻的事件是 query。
输出格式
对于每个 query 的事件,输出一行单个整数,表示该问题的答案。
样例
5 7
11011
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6
1
2
0
0
1
2
在这组样例中
时刻 |
路灯状态 |
询问 |
答案对应的时刻 |
1 |
11011 |
|
|
|
|
query 1 2 |
1 |
2 |
11011 |
|
|
|
|
query 1 2 |
1,2 |
3 |
11011 |
|
|
|
|
query 1 6 |
无 |
4 |
11011 |
|
|
|
|
query 3 4 |
无 |
5 |
11011 |
|
|
|
|
toggle 3 |
- |
6 |
11111 |
|
|
|
|
query 3 4 |
6 |
7 |
11111 |
|
|
|
|
query 1 6 |
6,7 |
数据范围与提示
对于全部数据,1≤n,q≤3×105,∣s∣=n,1≤i≤n,1≤a<b≤n+1。
详细子任务限制与分值如下表。
子任务 |
附加限制 |
分值 |
1 |
n,q≤100 |
20 |
2 |
对于所有 query a b 事件,满足 b−a=1 |
3 |
对于所有 toggle i 事件,第 i 个路灯将被点亮 |
4 |
所有 toggle 事件都发生在第一个 query 事件之前。 |
5 |
无特殊限制 |