CF1523G Try Booking

William 拥有一套位于伦敦市中心的公寓。他决定在接下来的 $n$ 天里将公寓出租以赚取一些收入。 由于他的公寓位于市中心，他立刻收到了 $m$ 个租房请求，每个请求的形式为 $(l_i, r_i)$，表示有人希望从第 $l_i$ 天起至第 $r_i$ 天（包含两端）租住公寓。为了避免花费大量时间判断接受某个请求是否划算，William 决定开发一个算法。该算法会按请求到达的顺序处理所有请求，并且仅当满足以下两个条件时才会接受第 $i$ 个请求： - $r_i - l_i + 1 \ge x$。 - 在 $l_i$ 到 $r_i$ 之间的所有天数中，没有一天已被之前接受的请求占用。 William 不确定 $x$ 应该取什么值，因此他请求你的帮助。对于所有 $x$ 从 $1$ 到 $n$，他希望你计算如果将 $x$ 设为对应值时，公寓将被占用的总天数。

第一行包含两个整数 $n$ 和 $m$，分别表示天数和请求数，满足 $1 \le n \le 5 \cdot 10^4, 1 \le m \le 10^5$。 接下来的 $m$ 行，每行包含两个整数 $l_i$ 和 $r_i$，表示第 $i$ 个租房请求，满足 $1 \le l_i \le r_i \le n$。所有请求按时间顺序给出。

输出 $n$ 个整数。第 $i$ 行的数字表示如果算法使用 $x = i$ 时，公寓将被占用的总天数。

第一个样例测试中各 $x$ 的区间描述如下： - $x = 1$ — 算法会接受请求：$1$（2..3），$3$（1..1）。公寓被出租的总天数为 3。 - $x = 2$ — 算法会接受请求：$1$（2..3）。公寓被出租的总天数为 2。 - $x = 3$ — 算法会接受请求：$2$（3..5）。公寓被出租的总天数为 3。 - $x = 4$ — 算法会接受请求：$4$（1..5）。公寓被出租的总天数为 5。 - $x = 5$ — 算法会接受请求：$4$（1..5）。公寓被出租的总天数为 5。 - $x = 6$ — 算法会接受请求：$5$（1..6）。公寓被出租的总天数为 6。 由 ChatGPT 4.1 翻译