题目描述

难度分:$1500$

输入$n(1 \leq n \leq 2 \times 10^5)$、$q(1 \leq q \leq 2 \times 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 2 \times 10^5)$。下标从$1$开始。

然后输入$q$个询问，每个询问输入两个数$L$和$R$，表示计算下标从$L$到$R$的连续子数组的元素和$(1 \leq L \leq R \leq 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]$相组合就能得到最大的查询结果总和$\Sigma_{i \in [1,n]}a[i] \times diff[i]$。

复杂度分析

时间复杂度

每个询问需要操作差分数组，时间复杂度为$O(q)$。对$a$、$diff$两个数组排序的时间复杂度为$O(nlog_2n)$。因此，整个算法的时间复杂度为$O(q+nlog_2n)$。

空间复杂度

除了输入的数组$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;
}