#P5829. [APIO2019] 路灯

    ID: 4830 传统题 3000ms 512MiB 尝试: 4 已通过: 2 难度: 9 上传者: 标签>数据结构树状数组算法基础分治线段树CF2800cdq分治

[APIO2019] 路灯

题目描述

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

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

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

给定时刻 00 的初始状态。第 ii 个小时是从时刻 i−1i-1 到时刻 ii 的一小时。在第 ii 个小时结束时发生一个事件,每小时恰有一个事件。

  • toggle i\text{toggle} \ i:切换第 ii 个路灯的状态。具体地说,若路灯原来亮起,则现在将熄灭;若路灯原来熄灭,则现在将亮起。
  • query a b\text{query} \ a \ b:出租车部门的负责人想知道,从时刻 00 到当前为止,出租车可以从站点 aa 到达站点 bb 的累计小时数。

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

输入格式

从标准输入读入数据。第一行包含两个整数 nn 和 qq,表示路灯的数量与时刻数。

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

接下来 qq 行每行描述一个时刻的事件。第 ii 行描述第 ii 个小时结束时的事件:

  • toggle i\text{toggle} \ i:切换第 ii 个路灯。新状态从下一个小时开始生效。
  • query a b\text{query} \ a \ b:计算至该小时结束为止,站点 aa 到站点 bb 的所有路段同时亮起的累计小时数。

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

输出格式

对于每个 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≤n,q≤3×1051 \leq n,q \leq 3\times 10^5,∣s∣=n|s|=n,1≤i≤n1 \leq i \leq n,1≤a<b≤n+11 \leq a < b \leq n+1。

详细子任务附加限制与分值如下表 (注:这里给出的子任务与本题在这里的最终评测无关,仅供参考)

子任务 附加限制 分值
1 nn, q≤100q\leq 100 20
2 对于所有 query a b\text{query}\ a\ b 事件,满足 a=b−1a=b-1
3 对于所有 toggle i\text{toggle}\ i 事件,第 ii 个路灯将被点亮
4 所有 toggle\text{toggle} 事件都发生在第一个 query\text{query} 事件之前
5 无特殊限制