#P5829. [APIO2019] 路灯
[APIO2019] 路灯
题目描述
一辆自动驾驶的出租车正在 Innopolis 的街道上行驶。该街道上有 个停车站点,它们将街道划分成了 条路段。每一路段都拥有一个路灯。当第 个路灯亮起,它将照亮连接第 与第 个站点的路段。否则这条路段将是黑暗的。
安全起见,出租车只能在被照亮的路段上行驶。换言之,出租车能从站点 出发到达站点 的条件是:连接站点 与 , 与 ,……, 与 的路段都被照亮。
在经过一些意外故障或修理之后,街道上的路灯可能是亮起的,也可能是熄灭的。
给定时刻 的初始状态。第 个小时是从时刻 到时刻 的一小时。在第 个小时结束时发生一个事件,每小时恰有一个事件。
- :切换第 个路灯的状态。具体地说,若路灯原来亮起,则现在将熄灭;若路灯原来熄灭,则现在将亮起。
- :出租车部门的负责人想知道,从时刻 到当前为止,出租车可以从站点 到达站点 的累计小时数。
请你帮助出租车部门的负责人回答他们的问题。
输入格式
从标准输入读入数据。第一行包含两个整数 和 ,表示路灯的数量与时刻数。
第二行包含一个字符串 表示路灯的初始状态, 为 表示第 个路灯初始时亮起; 为 表示第 个路灯初始时熄灭。
接下来 行每行描述一个时刻的事件。第 行描述第 个小时结束时的事件:
- :切换第 个路灯。新状态从下一个小时开始生效。
- :计算至该小时结束为止,站点 到站点 的所有路段同时亮起的累计小时数。
至少有一个时刻的事件是 。
输出格式
对于每个 query 事件,向标准输出写一行,一个整数,表示该问题的答案。
样例 #1
样例输入 #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 | 11011 |
query 1 2 |
1 |
| 2 | 1、2 | ||
| 3 | query 1 6 |
无 | |
| 4 | query 3 4 |
||
| 5 | toggle 3 |
— | |
| 6 | 11111 |
query 3 4 |
6 |
| 7 | query 1 6 |
6、7 |
数据范围
对于全部数据,,,,。
详细子任务附加限制与分值如下表 (注:这里给出的子任务与本题在这里的最终评测无关,仅供参考)
| 子任务 | 附加限制 | 分值 |
|---|---|---|
| 1 | , | 20 |
| 2 | 对于所有 事件,满足 | |
| 3 | 对于所有 事件,第 个路灯将被点亮 | |
| 4 | 所有 事件都发生在第一个 事件之前 | |
| 5 | 无特殊限制 |
相关
在下列比赛中: