CF276C Little Girl and Maximum Sum

小女孩非常喜欢数组查询相关的问题。 有一天，她碰到了一个相当著名的问题：你有一个包含 $n$ 个元素的数组（数组下标从 1 开始）；此外，还有 $q$ 个查询，每个查询由一对整数 $l_{i}$ 和 $r_{i}$ 定义（$1 \le l_{i} \le r_{i} \le n$）。你需要对于每个查询，求出数组下标从 $l_{i}$ 到 $r_{i}$（包含两端）之间所有元素的和。 小女孩认为这个问题太无聊了。她决定在回答查询之前，先重新排列数组元素，使得所有查询答案之和尽可能大。你的任务是求出这个最大总和的值。

第一行包含两个用空格分隔的整数 $n$（$1 \le n \le 2 \times 10^5$）和 $q$（$1 \le q \le 2 \times 10^5$），分别表示数组元素个数和查询数。 第二行包含 $n$ 个用空格分隔的整数 $a_{i}$（$1 \le a_{i} \le 2 \times 10^5$），表示数组的元素。 接下来的 $q$ 行中，每行包含两个用空格分隔的整数 $l_{i}$ 和 $r_{i}$（$1 \le l_{i} \le r_{i} \le n$），表示第 $i$ 个查询。

输出一行，一个整数，表示在重新排列数组元素后，所有查询答案之和的最大值。 请不要在 C++ 中使用 %lld 来读写 64 位整数。推荐使用 cin、cout 流或 %I64d 规范。

由 ChatGPT 5 翻译