【AcWing每日一题】4655. 重新排序

给定一个数组 A 和一些查询 Li,Ri，求数组中第 Li 至第 Ri 个元素之和。

小蓝觉得这个问题很无聊，于是他想重新排列一下数组，使得最终每个查询结果的和尽可能地大。

小蓝想知道相比原数组，所有查询结果的总和最多可以增加多少?
输入格式

输入第一行包含一个整数 n。

第二行包含 n 个整数 A1,A2,⋅⋅⋅,An，相邻两个整数之间用一个空格分隔。
第三行包含一个整数 m 表示查询的数目。

接下来 m 行，每行包含两个整数 Li、Ri，相邻两个整数之间用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。
数据范围

对于 30% 的评测用例，n,m≤50；

对于 50% 的评测用例，n,m≤500；
对于 70% 的评测用例，n,m≤5000；

对于所有评测用例，1≤n,m≤10⁵，1≤Ai≤10⁶，1≤L_i≤R_i≤n。

输入样例：

5
1 2 3 4 5
2
1 3
2 5

输出样例：

4

样例解释

原来的和为 6+14=20，重新排列为 (1,4,5,2,3) 后和为 10+14=24，增加了 4。

思路：

• 对区间的数进行操作，用到的是差分算法
• 如果对于每个询问都单独计算区间内的和，复杂度会到达O(n²)，会超时
  由于每次询问的区间对于数的操作只有一次，所以可以利用一个数组记录原数组每个位置的数的操作次数。这是对区间[l,r]内的每一个数都加c的操作，所以用到差分算法。
• 标记好操作次数之后，先用原数组的每一个数乘以每个数的操作次数得到原来的总和
  然后对于操作次数和原数组都按同样的顺序排序，这样，利用排序不等式原理，两个上升的数组的乘积和是最大的，从而得到最大的总和

• 两个总和一减就是答案

代码：

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5+10;
int a[N], s[N];     //a存储原数组， cnt用作s的差分，记录每个数的操作次数 
int n, m, k, l, r;
LL sum1, sum2;
int main(){
  cin >> n;
  for(int i = 1; i <= n; i++) cin >> a[i];
  cin >> m;
  for(int i = 0; i < m; i++){
    cin >> l >> r;
    s[l]++;
    s[r+1]--; 
  }
  for(int i = 1; i <= n; i++) s[i] += s[i-1];
  for(int i = 1; i <= n; i++) sum1 += (LL)s[i]*a[i];
  sort(s+1, s+n+1);
  sort(a+1, a+n+1);
  for(int i = 1; i <= n; i++) sum2 += (LL)s[i]*a[i];
  cout << sum2-sum1;
  return 0;
}