P7992 题解

xkcdjerry · 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。