[APIO2019]路灯

题目描述

一辆自动驾驶的出租车正在 Innopolis 的街道上行驶。该街道上有 $n+1$ 个停车站点,它们将街道划分成了 $n$ 条路段。每一路段都拥有一个路灯。当第 $i$ 个路灯亮起,它将照亮连接第 $i$ 与第 $i+1$ 个站点的路段。否则这条路段将是黑暗的。 安全起见,出租车只能在被照亮的路段上行驶。换言之,出租车能从站点 $a$ 出发到达站点 $b (a<b)$ 的条件是:连接站点 $a$ 与 $a+1$,$a+2$ 与 ,……,$b-1$ 与 $b$ 的路段都被照亮。 在经过一些意外故障或修理之后,街道上的路灯可能是亮起的,也可能是熄灭的。 现在给定 $0$ 时刻时,街道上路灯的初始状态。之后 $1,2,\ldots,q$ 时刻,每时刻会发生下列两种事件之一: - $\text{toggle} \ i$:切换第 $i$ 个路灯的状态。具体地说,若路灯原来亮起,则现在将熄灭;若路灯原来熄灭,则现在将亮起。 - $\text{query} \ a \ b$:出租车部门的负责人想知道,从 $0$ 时刻起到当前时刻,有多少个时刻满足:出租车能够从站点 $a$ 出发到达站点 $b$。 请你帮助出租车部门的负责人回答他们的问题。

输入输出格式

输入格式


第一行包含两个整数 $n$ 和 $q$—— 表示路灯的数量与时刻数。 第二行包含一个字符串 $s$ 表示路灯的初始状态, $s_i$ 为 $1$ 表示第 $i$ 个路灯初始时亮起;$s_i$ 为 $0$ 表示第 $i$ 个路灯初始时熄灭。 接下来 $q$ 行每行描述一个时刻的事件。第 $i$ 行描述时刻 $i$ 所发生的事件: - $\text{toggle} \ i$:该时刻切换了第 $i$ 个路灯的状态。 - $\text{query} \ a \ b$:计算从 $0$ 时刻起到该时刻,共有多少个时刻满足:出租车能从站点 $a$ 出发到达站点 $b$。 至少有一个时刻的事件是 $\text{query}$。

输出格式


对于每个 $\text{query}$ 的事件,输出一行单个整数,表示该问题的答案。

输入输出样例

输入样例 #1

5 7
11011
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6

输出样例 #1

1
2
0
0
1
2

说明

对于全部数据,$1 \leq n,q \leq 3\times 10^5,|s|=n,1 \leq i \leq n,1 \leq a < b \leq n+1$。 详细子任务附加限制与分值如下表 **(注:这里给出的子任务与本题在这里的最终评测无关,仅供参考)** | 子任务 | 附加限制 | 分值 | | :----------: | :----------: | :----------: | | 1 | $n$, $q\leq 100$ | 20 | | 2 | 对于所有 $\text{query}\ a\ b$ 事件,满足 $a=b-1$ | 20 | | 3 | 对于所有 $\text{toggle}\ i$ 事件,第 $i$ 个路灯将被点亮 | 20 | | 4 | 所有 $\text{toggle}$ 事件都发生在第一个 $\text{query}$ 事件之前 | 20 | | 5 | 无特殊限制 | 20 |