ABC353C Sigma Problem 题解
题目链接：AT
题目中的两个求和符号 \(\sum_{i=1}^{N-1} \sum_{j=i+1}^{N}\) 实际上是在枚举所有的有序数对 \((i, j)\)。而有序数对的个数 \(N(N-1)/2 = O(N^{2})\)，真的去枚举所有数对肯定会 T。这时应该考虑去拆贡献，求出每个 \(A_i\) 对答案的贡献。
这道题的一个要点是要注意到题目中 \(A_i \le 10^8\)。也就是说，对于任意的 \(A_i, A_j\)，要么 \(A_i + A_j < 10^8\)，此时有 \(f(A_i, A_j) = A_i + A_j\)；要么 \(10^8 \le A_i + A_j < 2 \times 10^8\)，此时有 \(f(A_i, A_j) = A_i + A_j - 10^8\)。
现在暂时不考虑第二种情况。这时所求的答案实际上就是枚举所有有序数对 \((i, j)\)，求和 \(A_i + A_j\)。因为每个 \(A_i\) 恰好出现在 \(N-1\) 个数对中，所以此时的答案是 \((N-1) \sum_{i=1}^{N} A_i\)。
（为什么每个 \(A_i\) 恰好出现在 \(N-1\) 个数对中？原因十分简单：因为我们枚举了所有的有序数对，所以每个 \(A_i\) 一定和除了它本身之外的所有 \(N-1\) 个元素都“配对”过一次，因此就出现在 \(N-1\) 个数对中。当然，因为是有序数对，可能 \(A_i\) 有时是数对的第一个元素，有时是数对的第二个元素，但这显然不影响答案。）
如果考虑第二种情况，最终的答案就要减去若干个 \(10^8\)。具体减去多少个呢？对于某个 \(A_i\)，找出所有满足 \(A_i + A_j \ge 10^8\) 且 \(j > i\) 的 \(j\) 的个数，那么答案就要减去这么多个 \(10^8\)。（这里限定 \(j > i\) 是因为题目中要求有序数对，不这么限定会导致重复计算。）于是可以先把 \(A\) 数组排序，对于某个 \(A_i\)，就可以二分查找出第一个满足\(A_i + A_j \ge 10^8\) 且 \(j > i\) 的 \(j\)，从而计算出所有满足的 \(j\) 的数量。
（为什么排序不会改变答案？要点在于题目中的 \(f(x, y)\) 函数满足“交换律”，或者说 \(f(x, y) = f(y, x)\)，所以可以随意调换数组元素的顺序而不改变答案。与之区分的是本场比赛的 D 题，那道题和本题很像，都是枚举所有的有序数对 \((i, j)\) 然后求值某个二元函数的函数值的和。但 D 题的函数不满足这种“交换律”，所以不能先排序再求和。）
综上，我们先求出所有 \(A_i\) 的和的 \(N-1\) 倍，再枚举所有的 \(A_i\)，找出应该减去多少个 \(10^8\) 即可。时间复杂度 \(O(N \log N)\)，瓶颈在排序和二分查找。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int MAXN = 3e5 + 10;
constexpr ll MOD = 1e8;
int n;
ll a[MAXN], ans, cnt;
int main()
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i], ans += (n-1) * a[i];
sort(a + 1, a + n + 1);
for(int i = 1; i < n; i++)
{
ll x = MOD - a[i];
int pos = lower_bound(a + i + 1, a + n + 1, x) - a; // 注意这里是从 a[i+1] 开始找的，这样能确保不会重复计算
cnt += n - pos + 1;
}
ans -= cnt * MOD;
cout << ans << endl;
return 0;
}