P4459.第2题-多多的宝物价值
题目内容
多多寻宝之旅来到了一个神秘的宝藏岛。岛上标注了 n 个地标, 每个地标都藏有一个价值不等的宝物。现在, 多多得到了一张古老的藏宝图, 上面记录了 q 个特殊的寻宝任务。每个任务都指定了一个地标的连续区间 [l,r] 。
你现在拥有所有地标的宝物价值, 但你可以自由地将它们重新排列。你的目标是找到一种最佳的排列方式, 使得所有 q 个任务的总收益最大化。
请根据以下输入, 计算并输出所有查询总和的最大值。
输入描述
第一行: 一个整数 n , 表示地标数量。
第二行: 一个整数 q , 表示查询数量。
第三行: 一个包含 n 个整数的数组 A, 表示每个地标的宝物价值。
接下来 q 行: 每行两个整数 l 和 r, 表示一个查询的区间, 其中 1<=l<=r<=n 。
约束条件
- n 的范围: 1≤n≤2∗105
- q 的范围: 1≤q≤2∗105
- 数组 A 中的元素: 每个宝物价值的绝对值不超过 109 。
- 查询范围 [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
