代码中 $d = x_d - x_c$

$sum[i][d]$ 的含义是 $[i, n]$ 的范围内有多少对差值为 $d$ 的二元组.

$pr[i][d]$ 的含义是 $[1, i]$ 的范围内有多少对差值为 $2d$ 的二元组.

思路是先枚举$X_a, X_b$， 通过 $sum$ 来统计不同的数作为 A 物品和 B 物品出现的次数，随后枚举$X_c,X_d$ 统计作为 C 物品和 D 物品出现的次数.

#include <bits/stdc++.h>
using namespace std;
const int N = 1.5e4 + 5;
int n, m, h[N], v[N][5], a[N], sum[N][N / 9], pr[N][N / 9];
int main() {
        scanf("%d %d", &n, &m);
        for (int i = 1; i <= m; ++i) {
                scanf("%d", &a[i]);
                h[a[i]]++;
        }
        for (int d = 1; d <= n / 9; ++d) {
                for (int i = n - d; i >= 1; --i)
                        sum[i][d] = sum[i + 1][d] + h[i] * h[i + d];
                for (int i = 2 * d + 1; i <= n; ++i)
                        pr[i][d] = pr[i - 1][d] + h[i] * h[i - 2 * d];
        }
        for (int i = 1; i <= n - 4; ++i)
                for (int j = i + 2; j <= n - 3; j += 2) {
                        if ((j - i) / 2 * 9 >= n) break;
                        int d = (j - i) / 2;
                        if (j + 6 * d + 1 > n) break;
                        v[i][1] += h[j] * sum[j + 6 * d + 1][d];
                        v[j][2] += h[i] * sum[j + 6 * d + 1][d];
                }
        for (int i = n; i > 3; --i)
                for (int j = i - 1; j > 2; --j) {
                        if ((i - j) * 9 >= n) break;
                        int d = i - j;
                        if (j - 6 * d - 1 < 1) break;
                        v[i][4] += h[j] * pr[j - 6 * d - 1][d];
                        v[j][3] += h[i] * pr[j - 6 * d - 1][d];
                }
        for (int i = 1; i <= m; ++i) 
                printf("%d %d %d %d\n", v[a[i]][1], v[a[i]][2], v[a[i]][3], v[a[i]][4]);
        return 0;
}