CF1965F Conference

你被要求组织一个非常重要的艺术会议。第一步是选择会议的日期。 会议必须持续若干连续的天数。每天必须有一位讲师进行演讲，并且同一位讲师不能在会议期间演讲超过一次。 你询问了 $n$ 位潜在讲师是否能够参加会议。第 $i$ 位讲师表示他们可以在第 $l_i$ 天到第 $r_i$ 天（包含两端）中的任意一天进行演讲。 如果存在一种方式，可以为该时间段内的每一天分配一位可用讲师，并且每位讲师最多只被分配一天，那么该时间段就可以作为会议日期。 对于每个 $k$ 从 $1$ 到 $n$，请你计算有多少种方式可以选择长度为 $k$ 的连续天数作为会议日期。

输入的第一行包含一个整数 $n$，表示潜在讲师的人数（$1 \le n \le 2 \cdot 10^5$）。 接下来的 $n$ 行，每行包含两个整数 $l_i$ 和 $r_i$，表示第 $i$ 位讲师可用的日期区间（$1 \le l_i \le r_i \le 2 \cdot 10^5$）。

输出 $n$ 个整数，第 $k$ 个数表示有多少种方式可以选择长度为 $k$ 的连续天数作为会议日期。

在第一个样例中，一天的会议可以在第 $1$ 天到第 $6$ 天中的任意一天举行。两天的会议可以在第 $2$ 天到第 $3$ 天，或者第 $4$ 天到第 $5$ 天举行。 在第二个样例中，五位讲师只能在第 $1$ 天到第 $3$ 天演讲，因此无法组织超过三天的会议。 由 ChatGPT 4.1 翻译