P6888: 复杂的间隔
传统题
1.000s
时间限制
256MB
内存限制
3 提交
0 解决
【题目描述】
【题目描述】
奶牛们正在努力尝试发明有趣的新游戏来玩。他们目前的工作之一与一组 N
个区间（1≤N≤2×10
^5
）有关，其中第 i 个区间从数轴上的 ai 位置开始，并在位置 bi≥ai 结束。ai 和 bi 均为 0…M 范围内的整数，其中 1≤M≤5000。
这个游戏的玩法是，Bessie
选择某个区间（假设是第 i 个区间），而她的表妹 Elsie 选择某个区间（假设是第 j 个区间，可能与 Bessie 所选的的区间相同）。给定某个值 k，如果 ai+aj≤k≤bi+bj
，则她们获胜。
对范围 0…2M
内的每个值 k，请计算使得 Bessie
和 Elsie 可以赢得游戏的有序对 (i,j) 的数量。
【
输入格式】
（从终端 /
标准输入读入）：
输入的第一行包含 N
和 M。以下 N
行每行以整数 ai 和 bi 的形式描述一个区间。
【
输出格式】
（输出至终端 /
标准输出）：
输出 2M+1
行，依次包含范围 0…2M 中的每一个 k 的答案。
【
输入样例】
：
2 5
1 3
2 5
【
输出样例】
：
0
0
1
3
4
4
4
3
3
1
1
在这个例子中，对于 k=3
，有三个有序对可以使得 Bessie
和 Elsie 获胜：(1,1)，(1,2)
，和 (2,1)
。
【
测试点性质】
：
测试点 1-2
满足 N≤100,M≤100。
测试点 3-5
满足 N≤5000。
测试点 6-20
没有额外限制。
注意输出可能无法用 32
位整数型存储，你可能需要使用 64 位整数型（例如，C 或 C++ 中的 "long long"）。