题目描述
难度分:1500
输入n(1≤n≤2×105)、q(1≤q≤2×105)和长为n的数组a(1≤a[i]≤2×105)。下标从1开始。
然后输入q个询问,每个询问输入两个数L和R,表示计算下标从L到R的连续子数组的元素和(1≤L≤R≤n)。
在计算之前,你可以重排a中的元素。输出所有询问结果总和的最大值。
输入样例1
3 3
5 3 2
1 2
2 3
1 3
输出样例1
25
输入样例2
5 3
5 2 4 1 3
1 5
2 3
2 3
输出样例2
33
算法
贪心+差分数组
贪心的思路很好想,哪个位置查得多,就把大的数排在这个位置。因此我们可以先计算每个位置查询了多少次,遍历每个询问(L,R),在区间[L,R]上加1,为了加速使用差分数组diff,这样可以O(q)处理所有询问,然后O(n)求个diff的前缀和就能知道每个位置查询了多少次。
知道每个位置i的查询次数diff[i],将diff和原数组a排序,相同排名的a[i]与diff[i]相组合就能得到最大的查询结果总和Σi∈[1,n]a[i]×diff[i]。
复杂度分析
时间复杂度
每个询问需要操作差分数组,时间复杂度为O(q)。对a、diff两个数组排序的时间复杂度为O(nlog2n)。因此,整个算法的时间复杂度为O(q+nlog2n)。
空间复杂度
除了输入的数组a,就开辟了一个同规模的数组diff。因此,额外空间复杂度为O(n)。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 200010;
int n, q, a[N], diff[N];
int main() {
scanf("%d%d", &n, &q);
diff[n + 1] = 0;
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
diff[i] = 0;
}
for(int i = 1; i <= q; i++) {
int l, r;
scanf("%d%d", &l, &r);
diff[l]++, diff[r + 1]--;
}
for(int i = 1; i <= n; i++) {
diff[i] += diff[i - 1];
}
sort(diff + 1, diff + n + 1);
sort(a + 1, a + n + 1);
LL ans = 0;
for(int i = 1; i <= n; i++) {
ans += 1LL * diff[i] * a[i];
}
printf("%lld\n", ans);
return 0;
}