loj#P3146. 「APIO2019」路灯

「APIO2019」路灯

题目描述

一辆自动驾驶的出租车正在 Innopolis 的街道上行驶。该街道上有 n+1n + 1 个停车站点,它们将街道划分成了 nn 条路段。每一路段都拥有一个路灯。当第 ii 个路灯亮起,它将照亮连接第 ii 与第 i+1i + 1 个站点的路段。否则这条路段将是黑暗的。

安全起见,出租车只能在被照亮的路段上行驶。换言之,出租车能从站点 aa 出发到达站点 b (a<b)b\ (a < b) 的条件是:连接站点 aaa+1a + 1a+1a + 1a+2a + 2,……,b1b − 1bb 的路段都被照亮。

在经过一些意外故障或修理之后,街道上的路灯可能是亮起的,也可能是熄灭的。

现在给定 00 时刻时,街道上路灯的初始状态。之后 1,2,,q1, 2,\ldots , q 时刻,每时刻会发生下列两种事件之一:

  • toggle i\texttt{toggle}\ i:切换第 ii 个路灯的状态。具体地说,若路灯原来亮起,则现在将熄灭;若路灯原来熄灭,则现在将亮起。
  • query a b\texttt{query}\ a\ b:出租车部门的负责人想知道,从 00 时刻起到当前时刻,有多少个时刻满足:出租车能够从站点 aa 出发到达站点 bb

请你帮助出租车部门的负责人回答他们的问题。

输入格式

第一行包含两个整数 nnqq——表示路灯的数量与时刻数。

第二行包含一个字符串 ss 表示路灯的初始状态,sis_i1 表示第 ii 个路灯初始时亮起;sis_i0 表示第 ii 个路灯初始时熄灭。

接下来 qq 行每行描述一个时刻的事件。第 ii 行描述时刻 ii 所发生的事件:

  • toggle i\texttt{toggle}\ i:该时刻切换了第 ii 个路灯的状态。
  • query a b\texttt{query}\ a\ b:计算从 00 时刻起到该时刻,共有多少个时刻满足:出租车能从站点 aa 出发到达站点 bb

至少有一个时刻的事件是 query\texttt{query}

输出格式

对于每个 query\texttt{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\le n,q\le 3\times 10^5,|s|=n,1\le i\le n,1\le a<b\le n+1$。

详细子任务限制与分值如下表。

子任务 附加限制 分值
11 n,q100n,q\le 100 2020
22 对于所有 query a b\texttt{query}\ a\ b 事件,满足 ba=1b - a = 1
33 对于所有 toggle i\texttt{toggle}\ i 事件,第 ii 个路灯将被点亮
44 所有 toggle\texttt{toggle} 事件都发生在第一个 query\texttt{query} 事件之前。
55 无特殊限制