5069. 画画的贝贝

单点时限: 5.0 sec

内存限制: 512 MB

贝贝的梦想是当一名画家。为了磨练技艺,贝贝不远万里地来到深山老林中请求伟大的画家 Andeviking 收他为徒。Andeviking 为了检验贝贝在画画上是否具有一定的天赋,决定出一道题来考验一下贝贝。

要想成为一名伟大的画家,对于色彩的敏感度并不可少。由于今天是疯狂星期四,贝贝想要V你50并请你写一个程序来帮助他通过考验。当然,没人能顶得住疯狂星期四的诱惑,所以请你帮帮他吧!

给定一面 颜色初始为 $1$ 长度为 $S$ 的墙壁,将其分为 $S$ 段,每段长度均为 $1$ 且 相邻段之间没有间隙 ,下标从左到右分别为 $1,2,\cdots,S$ 。接下来进行 $N$ 次操作,在每次操作中给出三个正整数 $L,R(L\le R)$ 以及颜色 $c$ ,意为将下标位于 $[L,R]$ 区间内(含 $L,R$ )的墙壁段 全部涂为颜色 $c$ (注意会覆盖之前的颜色) 。在每次操作后,请输出当前墙壁上的颜色种类总数。

(注意,每次操作不独立,即每次操作都是在上次操作后的基础上继续操作)

输入格式

数据共 $N+1$ 行,每行中数字用空格隔开

第一行有两个正整数 $S$ , $N$ ,分别为墙壁的长度与操作总数

第 $2$ ~ $N+1$ 行每行有三个正整数 $L$ , $R$ , $c$ ,分别为区间左右端点以及要涂的颜色

输出格式

共 $N$ 行,每行一个整数,表示当前墙壁上的颜色种类总数

样例

Input
5 5
1 4 2
2 4 3
1 5 2
2 3 1
3 4 2
Output
2
3
1
2
2
Input
5 5
5 5 3
1 4 1
2 2 3
1 4 1
1 2 2
Output
2
2
2
2
3

提示

$1 \leq S \leq 10^6$

$1 \leq N \leq 10^6$

$1 \leq L \leq R \leq S$

$1 \leq c \leq 10^6$

注意,本题输入输出量较大,建议使用较快读入输出方式。

54 人解决,77 人已尝试。

91 份提交通过,共有 218 份提交。

4.0 EMB 奖励。

创建: 10 月前.

修改: 10 月前.

最后提交: 9 月前.

来源: N/A

题目标签