loj#P3146. 「APIO2019」路灯
「APIO2019」路灯
题目描述
一辆自动驾驶的出租车正在 Innopolis 的街道上行驶。该街道上有 个停车站点,它们将街道划分成了 条路段。每一路段都拥有一个路灯。当第 个路灯亮起,它将照亮连接第 与第 个站点的路段。否则这条路段将是黑暗的。
安全起见,出租车只能在被照亮的路段上行驶。换言之,出租车能从站点 出发到达站点 的条件是:连接站点 与 , 与 ,……, 与 的路段都被照亮。
在经过一些意外故障或修理之后,街道上的路灯可能是亮起的,也可能是熄灭的。
现在给定 时刻时,街道上路灯的初始状态。之后 时刻,每时刻会发生下列两种事件之一:
- :切换第 个路灯的状态。具体地说,若路灯原来亮起,则现在将熄灭;若路灯原来熄灭,则现在将亮起。
- :出租车部门的负责人想知道,从 时刻起到当前时刻,有多少个时刻满足:出租车能够从站点 出发到达站点 。
请你帮助出租车部门的负责人回答他们的问题。
输入格式
第一行包含两个整数 和 ——表示路灯的数量与时刻数。
第二行包含一个字符串 表示路灯的初始状态, 为 1
表示第 个路灯初始时亮起; 为 0
表示第 个路灯初始时熄灭。
接下来 行每行描述一个时刻的事件。第 行描述时刻 所发生的事件:
- :该时刻切换了第 个路灯的状态。
- :计算从 时刻起到该时刻,共有多少个时刻满足:出租车能从站点 出发到达站点 。
至少有一个时刻的事件是 。
输出格式
对于每个 的事件,输出一行单个整数,表示该问题的答案。
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$。
详细子任务限制与分值如下表。
子任务 | 附加限制 | 分值 |
---|---|---|
对于所有 事件,满足 | ||
对于所有 事件,第 个路灯将被点亮 | ||
所有 事件都发生在第一个 事件之前。 | ||
无特殊限制 |