题目背景

原题为 P7992 [USACO21DEC] Convoluted Intervals S

题目描述

Gooby 养了一只猫（叫Ice⭐Meow），他正在和他的小猫玩一个区间游戏。

现在有 $N$ 个区间（$1\le N\le 2\cdot 10^5$），其中第 $i$ 个区间从数轴上的 $a_i$ 位置开始，并且在 $b_i$ 位置结束（保证 $b_i \ge a_i$）。$a_i$ 和 $b_i$ 均为 $0 \ldots M$ 范围内的整数，其中 $1 \leq M \leq 5000$。

这个游戏的玩法是，Gooby 选择某个区间（假设是第 $i$ 个区间），而小猫 Ice⭐Meow 选择某个区间（假设是第 $j$ 个区间，可能与 Gooby 所选的的区间相同）。给定某个值 $k$，如果 $a_i + a_j \leq k \leq b_i + b_j$，则她们获胜。

对范围 $0 \ldots 2M$ 内的每个值 $k$，请计算使得 Gooby 和 Ice⭐Meow 可以赢得游戏的有序对 $(i,j)$ 的数量。

输入格式

输入的第一行包含 $N$ 和 $M$。以下 $N$ 行每行以整数 $a_i$ 和 $b_i$ 的形式描述一个区间。

输出格式

输出 $2M+1$ 行，依次包含范围 $0 \ldots 2M$ 中的每一个 $k$ 的答案。

输入输出样例 #1

输入 #1

2 5
1 3
2 5

输出 #1

0
0
1
3
4
4
4
3
3
1
1

说明/提示

【样例解释】

在这个例子中，对于 $k=3$，有三个有序对可以使得 Gooby 和 Ice⭐Meow 获胜：$(1, 1)$，$(1, 2)$，和 $(2, 1)$。

【数据范围】

• 测试点 1-2 满足 $N\le 100, M\le 100$。
• 测试点 3-5 满足 $N\le 5000$。
• 测试点 6-20 没有额外限制。
• 对于所有测试点，保证 $1 \le N \le 2 \times 10^5, 1 \le M \le 5000$ $,0 \le a_i, b_i \le M$