Convoluted Intervals

题目描述

奶牛们正在努力发明一些有趣的新游戏来玩。她们当前的一项工作涉及一组 $N$ 个区间（$1\le N\le 2\cdot 10^5$）。第 $i$ 个区间在数轴上从位置 $a_i$ 开始，到位置 $b_i \geq a_i$ 结束。$a_i$ 和 $b_i$ 都是位于 $0 \ldots M$ 范围内的整数，其中 $1 \leq M \leq 5000$。

在游戏中，Bessie 选择某个区间（例如第 $i$ 个区间），她的表姐 Elsie 选择某个区间（例如第 $j$ 个区间，可能与 Bessie 选择的相同）。给定某个值 $k$，如果满足 $a_i + a_j \leq k \leq b_i + b_j$，她们就获胜。

对于范围 $0 \ldots 2M$ 内的每个 $k$，请统计有多少个有序对 $(i,j)$ 能使 Bessie 和 Elsie 赢得游戏。

输入格式

第一行输入包含 $N$ 和 $M$。接下来 $N$ 行中，每行用整数 $a_i$ 和 $b_i$ 描述一个区间。

输出格式

请输出 $2M+1$ 行，每行对应一个 $k$ 的值，$k$ 的范围为 $0 \ldots 2M$。

2 5
1 3
2 5

0
0
1
3
4
4
4
3
3
1
1

提示

在该示例中，仅对于 $k=3$，有三个有序对可以使 Bessie 和 Elie 获胜：$(1, 1)$、$(1, 2),$ 和 $(2, 1)$。

评分： 测试点 1-2 满足 $N\le 100, M\le 100$。 测试点 3-5 满足 $N\le 5000$。 测试点 6-20 没有额外限制。

注意输出值可能大到无法放入 32 位整数，因此你可能需要使用 64 位整数（例如 C 或 C++ 中的 "long long"）。 题目来源：Benjamin Qi

标签: USACO|2021|Silver

来源

USACO|2021|Silver