Processing math: 100%
编程题
                ### 问题描述

小蓝是一个热爱艺术的人,他有一串彩色气球,每个气球都有一个特定的颜色。他经常对这些气球进行染色以创造美丽的图案。现在,小蓝有 n 个气球,在一开始,全部都是 1 号色,他想通过一系列染色操作改变这些气球的颜色。

小蓝有 q 次操作,每次操作分为两步:

  1. 选择一个区间 [l,r]
  2. 将区间内的所有气球染成颜色 ci

小蓝希望你帮助他回答每次操作后,整个序列中有多少种不同的颜色。也就是,你需要计算每次操作后不同颜色的数量。

输入格式

第一行输入两个整数 n,q

接下来 q 行,每行三个整数 li,ri,ci,表示将 [li,ri] 的气球全部染色为 ci 颜色。

输出格式

输出 q 行,每次染色后,输出一个整数,表示现在的气球中有多少种颜色。

样例输入

5 3
1 2 2
1 1 3
1 5 3

样例输出

2
3
1

说明

  • 染色之前,5 个气球的颜色为 {1,1,1,1,1}
  • 第一次染色之后,5 个气球的颜色为 {2,2,1,1,1}
  • 第二次染色之后,5 个气球的颜色为 {3,2,1,1,1}
  • 第三次染色之后,5 个气球的颜色为 {3,3,3,3,3}

评测数据范围

1n,q105,1ci60,1lirin

查看答案
赣ICP备20007335号-2