自动搬运

查看原文

来自洛谷，原作者为

	xkcdjerry Wir müssen wissen. Wir werden wissen.

搬运于2025-08-24 22:34:59，当前版本为作者最后更新于2022-01-02 22:46:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先考虑显然做法：可以枚举 $a_i+a_j$ 和 $b_i+b_j$，那么显然每对 $i,j$ 之间的 $k$ 均可以通过此对 $i,j$ 取胜，则可以说 $i,j$ 对 $a_i+a_j$ 到 $b_i+b_j$ 这个区间的所有 $k$ 的答案贡献了 $1$。由于是区间加单点查询可以考虑使用差分数组维护。总复杂度为 $O(n^2)$。

这里发现 $n$ 非常大但是值域 $m$ 很小，可以开桶维护。

令 $fa_x$ 为 $a_i=x$ 的数目，$fb_x$ 为 $b_i=x$ 的数目，那么由于前缀和的原理可以分别处理所有 $a_i+a_j$ 和所有 $b_i+b_j$。

对于 $a$ 数组，由于对于任意 $x,y$ 都有 fa[x] 个不同的 $i$ 使得 $a_i=x$，fa[y] 个 $j$ 使得 $a_j=y$，那么对 $x+y$ 产生的总贡献就是 $fa_x \times fa_y$。

$b$ 数组同理，记得因为前缀和的原理所以贡献要加在 $x+y+1$ 的位置上。

最后把差分数组做前缀和即可得到答案。

#include <cstdio>
#define M 5010
#define N 200010
long long f[2*M];
long long fa[M],fb[M];
int n,m;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        fa[a]++;
        fb[b]++;
    }
    for(int i=0;i<=m;i++)
        for(int j=0;j<=m;j++)
        {
            f[i+j]+=fa[i]*fa[j];
            f[i+j+1]-=fb[i]*fb[j];
        }
    long long ans=0;
    for(int i=0;i<=2*m;i++)
        printf("%lld\n",ans+=f[i]);
}

特别提醒：一定要么全部开 long long；要么 f 和 ans 开 long long，fa 和 fb 乘的时候转 long long，否则会收获 95 分的好成绩！！！