Convoluted Intervals (USACO Silver 2021 December)

首先应该比较直观可以想到 $\mathcal{O}(N^2)$ 的朴素算法： $(a[i],b[i])$ 两两组合，直接用差分来求和。也就是在 $[a[i]+a[j], b[i]+b[j]]$ 区间上都加一，最后打印出来就可以了，可惜这个只能得10%的分。

然后我们优化这个算法，观察到 $M$ 最大是5000，是这个题主要的优化机会。因为 $M$ 很小，所以上面 $a[i]+a[j]$ 的值一共只有10000种，因此枚举所有可能的值，对每个值，统计有多少个 $a[i]+a[j]$ 等于这个值，然后把数量加到差分数组上。然后对 $b[i]+b[j]$ 的值也做同样的事情。最后用前缀和求出每个位置的值，就可以了。

总体还是比较直观的，代码中有一个需要注意越界的地方。

📙 Convoluted Intervals讲解幻灯片

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n, m;
int a[200005], b[200005];
ll cnta[10005], cntb[10005];   // 5005不够，小心下面cnt?[j]和cnt?[i-j]越界
ll diff[10005];
 
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        scanf("%d", &b[i]);
        cnta[a[i]]++;
        cntb[b[i]]++;
    }
    for (int i = 0; i <= 2*m; i++)
        for (int j = 0; j <= i; j++) {
            diff[i] += cnta[j] * cnta[i-j];
            diff[i+1] -= cntb[j] * cntb[i-j];
        }
    ll ans = 0;
    for (int i = 0; i <= 2*m; i++) {
        ans += diff[i];
        printf("%lld\n", ans);
    }
 
    return 0;
}