解题思路

• 用差分数组统计每个位置被所有区间覆盖的次数。对每个查询 [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 同序排序后逐项相乘求和，即为答案。

复杂度分析

题目内容

多多寻宝之旅来到了一个神秘的宝藏岛。岛上标注了 $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$