【每日一题】ARC071D - ### | 前缀和 | 简单
题目内容
原题链接
给定一个长度为 n n n 的数组 a a a 和一个长度为 m m m 的数组 b b b 。
从数组 a a a 中挑出两个数，作为两条平行于 y y y 轴的直线，数组 b b b 中挑出两个数，作为两条平行于 x x x 轴的直线，问这四条直线构成的矩形的面积。
你需要所有可能的矩形的面积之和，答案对 1 0 9 + 7 10^9+7 109+7 取模
数据范围
- 2 ≤ n , m ≤ 2 ⋅ 1 0 5 2\leq n,m\leq 2\cdot 10^5 2≤n,m≤2⋅105
- − 1 0 9 ≤ a i , b i ≤ 1 0 9 -10^9\leq a_i,b_i\leq 10^9 −109≤ai,bi≤109
题解
先对两个数组排序，下标从 0 0 0 开始。
对于数组 a a a ，每个数 a i a_{i} ai，考虑比其小的数的和为 p r e a i − 1 prea_{i-1} preai−1，一共有 i i i 个数比 a i a_i ai 小（小于等于），那么和 a i × i − p r e a i − 1 a_i\times i-prea_{i-1} ai×i−preai−1。
对于数组 b b b 也一样。
但是这里需要考虑的是，对于每个数 a i a_i ai ，其需要与数组 b b b 中任意两个数构成的直线进行计算。
所以考虑 p p r e b i = ∑ j = 0 i b i × p r e b i − 1 ppreb_{i}=\sum\limits_{j=0}^i b_i\times preb_{i-1} pprebi=j=0∑ibi×prebi−1
最后答案就是： ∑ i = 0 n − 1 ( a i × i − p r e a i − 1 ) × p p r e b n − 1 \sum\limits_{i=0}^{n-1} (a_i\times i-prea_{i-1})\times ppreb_{n-1} i=0∑n−1(ai×i−preai−1)×pprebn−1
时间复杂度： O ( n ) O(n) O(n)
代码
#include <bits/stdc++.h>
using namespace std;typedef long long ll;const int MOD = 1e9 + 7;int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int n, m;cin >> n >> m;vector<ll> a(n), b(m);for (int i = 0; i < n; ++i) cin >> a[i];for (int i = 0; i < m; ++i) cin >> b[i];sort(a.begin(), a.end());sort(b.begin(), b.end());ll prea = (a[0] % MOD + MOD) % MOD;ll preb = (b[0] % MOD + MOD) % MOD, ppreb = 0;for (int i = 1; i < m; ++i) {ppreb += b[i] * i - preb;ppreb = (ppreb % MOD + MOD) % MOD;preb += b[i];preb %= MOD;}ll ans = 0;for (int i = 1; i < n; ++i) {ll cur = ((a[i] * i - prea) % MOD + MOD) % MOD;ans = (ans + cur * ppreb % MOD) % MOD;prea += a[i];prea %= MOD;}cout << ans << "\n";return 0;
}