【USACO2021 Convoluted Intervals 】题解

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15716558.html

题目

The cows are hard at work trying to invent interesting new games to play. One of
their current endeavors involves a set of $N$ intervals
($1\le N\le 2\cdot 10^5$), where the $i$th interval starts at position $a_i$ on
the number line and ends at position $b_i \geq a_i$. Both $a_i$ and $b_i$ are
integers in the range $0 \ldots M$, where $1 \leq M \leq 5000$.

To play the game, Bessie chooses some interval (say, the $i$th interval) and her
cousin Elsie chooses some interval (say, the $j$th interval, possibly the same
as Bessie’s interval). Given some value $k$, they win if
$a_i + a_j \leq k \leq b_i + b_j$.

For every value of $k$ in the range $0 \ldots 2M$, please count the number of
ordered pairs $(i,j)$ for which Bessie and Elsie can win the game.

奶牛们正在努力尝试发明有趣的新游戏来玩。他们目前的工作之一与一组 $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$，请计算使得 Bessie 和 Elsie 可以赢得游戏的有序对 $(i,j)$ 的数量。

思路

用差分思想考虑，所有 $a_i+a_j$ 的地方+1，所以 $b_i+b_j+1$ 的地方减1。

然而这是 $O(n^2)$，但我们发现 $a,b$ 的值域很小，所以我们可以用桶存起来，然后按值域遍历即可，就变成 $O(m^2)$。

总结

对于一些过于重复的计算，如果值域很小，我们可以尝试用桶存起来，减去很多过于重复的计算。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 5010
int n, m, i, j, k; 
int a[N], b[N], x[N], y[N], c[N*2]; 

signed main()
{
	scanf("%lld%lld", &n, &m); 
	for(i=1; i<=n; ++i) scanf("%lld%lld", &j, &k), x[j]++, y[k]++; 
	for(i=0; i<=m; ++i)
		for(j=0; j<=m; ++j)
			c[i+j]+=x[i]*x[j], c[i+j+1]-=y[i]*y[j]; 
	for(i=k=0; i<=2*m; ++i) printf("%lld\n", k+=c[i]); 
	return 0;
}