所有排列中的最大和

/*
 * 思路：
 * 1. 对于每个请求区间，记录每个索引被请求的频率。
 * 2. 通过计算每个索引的请求次数，确定索引的权重。
 * 3. 将数组和权重排序，权重越大对应的数组值应越大。
 * 4. 将排序后的数组和权重一一对应相乘，得到最大查询和。
 * 5. 将结果对10^9 + 7取余后返回。
 */
import java.util.*;
import java.util.stream.*;

public class Solution {
    public int maxSumRangeQuery(int[] nums, int[][] requests) {
        int n = nums.length;
        int mod = 1000000007;
        int[] freq = new int[n];
        
        // 记录每个索引被请求的频率
        for (int[] req : requests) {
            freq[req[0]]++;
            if (req[1] + 1 < n) freq[req[1] + 1]--;
        }
        
        // 前缀和计算实际频率
        for (int i = 1; i < n; i++) {
            freq[i] += freq[i - 1];
        }
        
        // 排序
        Arrays.sort(nums);
        freq = Arrays.stream(freq).sorted().toArray();
        
        // 计算结果
        long result = 0;
        for (int i = 0; i < n; i++) {
            result = (result + (long) nums[i] * freq[i]) % mod;
        }
        
        return (int) result;
    }
}