thz 的抽奖箱
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
thz 有 $n$ 个抽奖箱，编号为 $1 \sim n$，一开始每个抽奖箱都是空的抽奖箱内可以被放入一些有编号的小球，保证所有小球除了编号以外完全相同
我们认为一个抽奖箱内，连续编号的小球越多，则幸运度越高
连续编号是指一些小球的编号能组成差值为 $1$ 的等差数列
一个抽奖箱的幸运度定义为: 这个抽奖箱内最长的连续编号小球数量
例如一个抽奖箱内存在以下五个小球: $2,4,5,6,8$，那么这个抽奖箱的幸运度即为 $3$
现在 thz 每次可以在编号区间为 $[l, r]$ 的抽奖箱内同时加入编号为 $x$ 的小球
现在 thz 想知道，当他进行完所有操作以后，每个抽奖箱的幸运度是多少？
输入格式
第一行包含两个整数 $n,m$，表示有 $n$ 个抽奖箱有 $m$ 次操作接下来 $m$ 行每行包含三个数字 $l,r,x$，表示 thz 这次操作会在编号为 $[l,r]$ 的每个抽奖箱内都加入编号为 $x$ 的小球
对于 $30\%$ 的数据, $n,m \leq 1000$
对于另外 $30\%$ 的数据, $l,r$ 随机。
对于 $100\%$ 的数据, $n,m \leq 100000,1 \leq x \leq 10^9$
数据保证除 $100\%$ 的数据其他数据没有交集
题目保证同一个编号的小球不会被多次放入一个抽奖箱
输出格式
只有一行包含 $n$ 个整数，分别表示每个抽奖箱的幸运度样例
10 10
1 2 1
1 2 2
1 2 3
1 2 4
1 3 5
3 4 6
3 4 7
3 4 8
3 4 9
3 10 105 5 6 5 1 1 1 1 1 120231230提高组班级模拟赛
- 状态
- 已结束
- 规则
- ACM/ICPC
- 题目
- 3
- 开始于
- 2023-12-30 22:00
- 结束于
- 2024-1-8 6:00
- 持续时间
- 200 小时
- 主持人
-
huangzhe
- 参赛人数
- 11
