总结

难难难难难！！！

0 + 0 + 35 = 35（~~呃呃呃呃这都能得第五~~

T1

大概是提高组第三题（?

T2

很有趣的一道提高组第二题

T3

提高组第一题（?

看到这道题，肯定会想到枚举每一组 \([i,j]\) 在枚举 \([a_i + a_j,b_i+b_j]\) 中的每一个数，然后依次加一，这样做的时间复杂度是 \(O(n ^ 2 \cdot m)\) 肯定过不了，需要优化！观察一下思路，发现枚举枚举每一个数然后加一的步骤似乎可以用差分来完成，于是时间复杂度就变成了 \(O(n ^ 2)\)，可是 \(n\) 有 \(2 \times 10 ^ 5\)，依然过不了，再回去读一遍题，发现 \(m\) 只有 \(5 \times 10 ^ 3\)，\(m ^ 2\) 都能过，那我们肯定要在 \(m\) 上做文章，我们想到当 \(m = k\) 时的方案数就是 \(a_i + a_j\) 满足的数减去 \(b_i+b_j\)的不满足方案数，于是可以双重循环枚举每一个在 \(m\) 以内的 \(i\) 和 \(j\)，那么可以凑出的方案个数就是 \(cnt1_{i} \cdot cnt1_{j}\)（\(cnt1_{a[i]}\) 表示 \(a[i]\) 的个数），再用一个差分数组即可 \(AC\)

code：
时间复杂度：\(O(m^2)\)
空间复杂度：\(O(m)\)

#include <bits/stdc++.h>

using namespace std;

#define int long long 

const int N = 1e4 + 5;

int n, m, cnt1[N], cnt2[N], ans1[N], ans2[N];

signed main() {
  cin >> n >> m;
  for (int i = 1, a, b; i <= n; i++) {
    cin >> a >> b;
    cnt1[a]++, cnt2[b]++;
  }  
  for (int i = 0; i <= m; i++) {
    for (int j = 0; j <= m; j++) {
      ans1[i + j] += cnt1[i] * cnt1[j];
      ans2[i + j + 1] -= cnt2[i] * cnt2[j];
    }
  }
  for (int i = 1; i <= 2 * m; i++) {
    ans1[i] += ans1[i - 1];
    ans2[i] += ans2[i - 1];
  }
  for (int i = 0; i <= 2 * m; i++) {
    cout << ans1[i] + ans2[i] << "\n";
  }
  return 0;
}