AdditionalFile5657.zip

#5657. 「POI2026 R3」Deszcze meteorów

标签: 传统 | 时间限制: 7000 ms | 内存限制: 512 MiB |

题目描述

题目译自 XXXIII Olimpiada Informatyczna – III etap Deszcze meteorów

比特托邦的秋天已经开始。夜晚变得越来越长、越来越冷，居民们不安地注视着天空，因为在接下来的 $n$ 天里预计会出现流星雨。对于每一天，我们已知若干个互不相交的毫秒区间，在这些区间内预计会有流星雨。总共有 $m$ 个这样的区间。

拜塔扎尔考虑在接下来的 $n$ 天中的某一天开始观测流星。为此，他希望选择一个开始观测的日期 $i$，以及一个观测时刻 $t$（以毫秒为单位）。我们的主人公将在接下来的连续日期（$i, i+1, i+2, \ldots$）中进行观测，只要在这些日子的时刻 $t$ 都有流星雨发生。换句话说，在 $i, i+1, i+2, \ldots$ 这些日子中，拜塔扎尔将在第一个时刻 $t$ 没有流星雨的日子停止观测。

拜塔扎尔还不确定在哪一天开始观测。因此，他请你为每一个起始日期 $i$，计算出在符合上述条件的情况下，他能够连续观测流星雨的最大天数。若第 $i$ 天没有任何流星雨发生，则所求的最大天数为 $0$。

输入格式

第一行包含两个整数 $n$ 和 $m$ $(1 \leq n, m \leq 500000)$，分别表示天数和区间总数。

接下来的 $m$ 行中，每行包含三个整数 $d, x$ 和 $y$ $(1 \leq d \leq n, 0 \leq x < y \leq 86400000)$，表示在第 $d$ 天预计会有流星雨，它从第 $x$ 毫秒开始，并在第 $y$ 毫秒前结束。你可以假设同一天的给定区间是两两不相交的。

输出格式

你的程序应当输出 $n$ 行。第 $i$ 行包含一个整数，表示从第 $i$ 天开始、且每天在同一时刻观测的情况下，能够连续观测流星的最大天数。

样例

输入

5 7
4 2 4
1 3 7
3 4 8
2 6 9
2 2 4
5 1 6
4 7 9

输出

3
3
2
2
1

对于连续的日期，观测可以分别在以下时刻（以毫秒为单位）进行：$6, 7, 7, 2$ 和 $1$。下图展示了每一天代表流星雨的区间，并用阴影标注了对应于所选观测时刻的区域。请注意，第二天的区间覆盖了第三天的区间。

附加样例

• $\texttt{0a}$：即为上述样例。
• $\texttt{0b}$：$n=m=500000, d_i=i, x_i=i, y_i=2i$。
• $\texttt{0c}$：$n=1000$，偶数日有 $2$ 个区间，奇数日有 $1$ 个区间。
• $\texttt{0d}$：$n=100, y_i \leq 1000$，第 $i$ 天包含 $i \bmod 20$ 个区间。

数据范围与提示

详细子任务附加限制及分值如下表所示。