解题思路

• 用差分数组统计每个位置被所有区间覆盖的次数。对每个查询 [l, r]（1-based）：

  • 设 L = l-1（0-based），R = r-1，则执行 diff[L] += 1、diff[R+1] -= 1（为防越界，diff 开到 n+1）。
  • 最后对 diff 做前缀和，得到频次数组 freq[i]，表示位置 i 被查询的总次数。

• 根据重排不等式：为了最大化点乘，总应把两数组同序排序（均升序或均降序）。因此将宝物价值数组 A 与频次数组 freq 同序排序后逐项相乘求和，即为答案。

复杂度分析

• 时间复杂度：O(n + q + n log n)，差分与前缀和 O(n+q)，排序 O(n log n)。
• 空间复杂度：O(n)，用于差分与频次数组。

代码实现

Python

# 功能函数：返回最大总和
def maximize_sum(n, q, A, intervals):
    # 差分数组，开到 n+1，支持对 R+1 位置的 -1 操作
    diff = [0] * (n + 1)
    for l, r in intervals:
        L = l - 1  # 0-based
        R = r - 1
        diff[L] += 1
        diff[R + 1] -= 1

    # 前缀和得到每个位置被覆盖的次数
    freq = [0] * n
    cur = 0
    for i in range(n):
        cur += diff[i]
        freq[i] = cur

    # 同序排序，按重排不等式最大化点乘
    A.sort()
    freq.sort()

    # 计算答案（Python 自动处理大整型，题目保证不超 64 位）
    ans = 0
    for i in range(n):
        ans += A[i] * freq[i]
    return ans

def main():
    import sys
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    n = next(it)
    q = next(it)
    A = [next(it) for _ in range(n)]
    intervals = [(next(it), next(it)) for _ in range(q)]
    print(maximize_sum(n, q, A, intervals))

if __name__ == "__main__":
    main()

Java

// 类名必须为 Main（ACM 风格）
import java.io.*;
import java.util.*;

public class Main {
    // 功能函数：返回最大总和（使用 long，题目保证结果不超 64 位）
    static long maximizeSum(int n, int q, long[] A, int[][] intervals) {
        long[] diff = new long[n + 1]; // 差分数组，长度 n+1

        // 处理区间 [l, r]（1-based），对应 0-based [L, R]
        for (int i = 0; i < q; i++) {
            int l = intervals[i][0], r = intervals[i][1];
            int L = l - 1; // 0-based
            int Rp1 = r;   // R+1 的 0-based 索引
            diff[L] += 1;
            diff[Rp1] -= 1; // Rp1 可能等于 n，合法
        }

        // 前缀和得到覆盖次数
        long[] freq = new long[n];
        long cur = 0;
        for (int i = 0; i < n; i++) {
            cur += diff[i];
            freq[i] = cur;
        }

        // 同序排序（升序）
        Arrays.sort(A);
        Arrays.sort(freq);

        // 计算答案
        long ans = 0;
        for (int i = 0; i < n; i++) {
            ans += A[i] * freq[i];
        }
        return ans;
    }

    // 简单高效的输入（根据数据规模采用快读）
    static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;

        FastScanner(InputStream is) { this.in = is; }

        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }

        long nextLong() throws IOException {
            int c; long sgn = 1, val = 0;
            do { c = read(); } while (c <= 32);
            if (c == '-') { sgn = -1; c = read(); }
            while (c > 32) {
                val = val * 10 + (c - '0');
                c = read();
            }
            return val * sgn;
        }

        int nextInt() throws IOException { return (int) nextLong(); }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        int n = fs.nextInt();
        int q = fs.nextInt();

        long[] A = new long[n];
        for (int i = 0; i < n; i++) A[i] = fs.nextLong();

        int[][] intervals = new int[q][2];
        for (int i = 0; i < q; i++) {
            intervals[i][0] = fs.nextInt();
            intervals[i][1] = fs.nextInt();
        }

        long ans = maximizeSum(n, q, A, intervals);
        System.out.println(ans);
    }
}

C++

// ACM 风格：输入输出在主函数，核心逻辑在外部函数
#include <bits/stdc++.h>
using namespace std;

// 功能函数：返回最大总和（long long 即可）
long long maximize_sum(int n, int q, vector<long long>& A, const vector<pair<int,int>>& intervals) {
    // 差分数组，长度 n+1，便于对 R+1 位置做 -1
    vector<long long> diff(n + 1, 0);

    // 处理每个区间 [l, r]（1-based）
    for (auto &pr : intervals) {
        int l = pr.first, r = pr.second;
        int L = l - 1; // 0-based
        int Rp1 = r;   // R+1 的 0-based 索引
        diff[L] += 1;
        diff[Rp1] -= 1; // Rp1 可能等于 n，安全
    }

    // 前缀和得到覆盖次数
    vector<long long> freq(n, 0);
    long long cur = 0;
    for (int i = 0; i < n; ++i) {
        cur += diff[i];
        freq[i] = cur;
    }

    // 同序排序（升序）
    sort(A.begin(), A.end());
    sort(freq.begin(), freq.end());

    // 计算答案
    long long ans = 0;
    for (int i = 0; i < n; ++i) {
        ans += A[i] * freq[i];
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    if (!(cin >> n)) return 0;
    cin >> q;

    vector<long long> A(n);
    for (int i = 0; i < n; ++i) cin >> A[i];

    vector<pair<int,int>> intervals(q);
    for (int i = 0; i < q; ++i) {
        int l, r; cin >> l >> r;
        intervals[i] = {l, r};
    }

    long long ans = maximize_sum(n, q, A, intervals);
    cout << ans << '\n';
    return 0;
}

题目内容

多多寻宝之旅来到了一个神秘的宝藏岛。岛上标注了 $n$ 个地标, 每个地标都藏有一个价值不等的宝物。现在, 多多得到了一张古老的藏宝图, 上面记录了 $q$ 个特殊的寻宝任务。每个任务都指定了一个地标的连续区间 $[l, r]$ 。

你现在拥有所有地标的宝物价值, 但你可以自由地将它们重新排列。你的目标是找到一种最佳的排列方式, 使得所有 $q$ 个任务的总收益最大化。

请根据以下输入, 计算并输出所有查询总和的最大值。

输入描述

第一行: 一个整数 $n$ , 表示地标数量。

第二行: 一个整数 $q$ , 表示查询数量。

第三行: 一个包含 $n$ 个整数的数组 $A$, 表示每个地标的宝物价值。

接下来 $q$ 行: 每行两个整数 $l$ 和 $r$, 表示一个查询的区间, 其中 $1 <= l <= r <= n$ 。

约束条件

• $n$ 的范围: $1 ≤ n ≤ 2 * 10^5$
• $q$ 的范围: $1 ≤ q ≤ 2 * 10^5$
• 数组 $A$ 中的元素: 每个宝物价值的绝对值不超过 $10^9$ 。
• 查询范围 $[l, r]: 1 <= l <= r <= n$

输出描述

一个整数, 表示所有查询总和的最大值。

样例1

输入

3
2
1 2 3
1 2
1 3

输出

11

说明

• 每个地标的查询次数是 $[2, 2, 1]$
• 最佳的宝物价值排列是 $[3, 2, 1]$
• 所有查询总和 $=$ (地标 $1$ 的宝物价值 $×$ 地标 $1$ 的查询次数) $+$ (地标 $2$ 的宝物价值 $×$ 地标 $2$ 的查询次数) $+$ (地标 $3$ 的宝物价值 $×$ 地标 $3$ 的查询次数) $= (3×2)+(2×2)+(1×1)=11$