P14268 [ROI 2015 Day2] 路灯

**译自 [ROI 2015](https://neerc.ifmo.ru/school/archive/2014-2015.html) Day2 T3.** ***[Фонари](https://neerc.ifmo.ru/school/archive/2014-2015/ru-olymp-roi-2015-day2.pdf)***

在“水下运河”街上共有 $n$ 盏路灯，沿街从 1 到 $n$ 编号。连续的一段路灯称为一个**区段**。因此，总的区段数量等于 $\frac{n(n+1)}{2}$。如果某个区段内的所有路灯都亮着（即灯泡完好），则称该区段为**正常工作**的。 路灯上可能发生两种类型的事件： 1. 某个区段由于电压波动导致其中所有灯泡同时烧坏； 2. 能源公司选择某个区段，派出维修人员更换该区段内所有烧坏的灯泡，使其恢复正常。 在每次事件发生后，市政$ $府都会要求提交一份报告，说明当前**正常工作的区段数量**。为了提升业绩指标，维修部门在报告中会包含所有**现在正常**或**曾经正常**的区段。 请你编写一个程序，在每次事件之后，计算到目前为止（包括此次事件）**当前正常或曾经正常**的区段数量。

第一行包含两个整数 $n$ 和 $q$ —— 分别表示路灯的数量和事件的数量。 第二行包含一个由 $n$ 个字符组成的字符串，仅包含 **0** 和 **1**： - **1** 表示该路灯灯泡完好； - **0** 表示该路灯灯泡已烧坏。 接下来 $q$ 行中，每行包含三个整数 $l_i, r_i, c_i$，表示一次事件： - 若 $c_i = 0$，则编号从 $l_i$ 到 $r_i$（包含两端）的所有路灯灯泡全部烧坏； - 若 $c_i = 1$，则编号从 $l_i$ 到 $r_i$ 的所有灯泡全部更换为新的、完好的灯泡。 保证 $1 \le l_i \le r_i \le n$，且 $c_i$ 仅取值 0 或 1。

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

### 数据范围 | 子任务编号 | 分值 | $n$ 范围 | $q$ 范围 | |:--:|:--:|:--:|:--:| | 1 | 17 | $1 \le n \le 50$ | $1 \le q \le 150$ | | 2 | 19 | $1 \le n \le 500$ | $1 \le q \le 250$ | | 3 | 12 | $1 \le n \le 5000$ | $1 \le q \le 1000$ | | 4 | 20 | $1 \le n \le 50\,000$ | $1 \le q \le 1000$ | | 5 | 32 | $1 \le n \le 300\,000$ | $1 \le q \le 300\,000$ |