logo AlgoBeat OnlineJudge
登录 注册

#214375. [ROI 2015 Day2] 路灯

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

译自 ROI 2015 Day2 T3. Фонари


在“水下运河”街上共有 盏路灯,沿街从 1 到 编号。连续的一段路灯称为一个区段。因此,总的区段数量等于 。如果某个区段内的所有路灯都亮着(即灯泡完好),则称该区段为正常工作的。

路灯上可能发生两种类型的事件:

  1. 某个区段由于电压波动导致其中所有灯泡同时烧坏;
  2. 能源公司选择某个区段,派出维修人员更换该区段内所有烧坏的灯泡,使其恢复正常。

在每次事件发生后,市政府都会要求提交一份报告,说明当前正常工作的区段数量。为了提升业绩指标,维修部门在报告中会包含所有现在正常曾经正常的区段。

请你编写一个程序,在每次事件之后,计算到目前为止(包括此次事件)当前正常或曾经正常的区段数量。

输入格式

第一行包含两个整数 —— 分别表示路灯的数量和事件的数量。

第二行包含一个由 个字符组成的字符串,仅包含 01

  • 1 表示该路灯灯泡完好;
  • 0 表示该路灯灯泡已烧坏。

接下来 行中,每行包含三个整数 ,表示一次事件:

  • ,则编号从 (包含两端)的所有路灯灯泡全部烧坏;
  • ,则编号从 的所有灯泡全部更换为新的、完好的灯泡。

保证 ,且 仅取值 0 或 1。

输出格式

第一行输出一个整数 —— 初始状态下正常工作的区段数量。接下来输出 行,第 行输出在第 次事件之后,所有当前正常或曾经正常的区段数量。

样例

样例输入 1

7 4
1100101
4 6 1
3 6 0
3 4 1
5 7 1

样例输出 1

5
13
13
19
28

数据范围与提示

数据范围

子任务编号 分值 范围 范围
1 17
2 19
3 12
4 20
5 32