一、题目
1、原题链接
4655. 重新排序 - AcWing题库
2、题目描述
给定一个数组 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^5，1≤Ai≤10^6，1≤Li≤Ri≤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。
二、解题报告
思路来源：up主，可以解释一下众人拾柴火焰高的含义吗？每日一题_哔哩哔哩_bilibiliy总yyds
1、思路分析
1）先创建一个数组来记录各个位置上的数需要被加多少次，初识化都是0，可以利用差分，对每次对给定区间上的数+1。
2）对差分后的数组求前缀和，即可得到一个记录了各个位置需要被加多少次的数组。
3）对原数组和2）中求得的数组，每项相乘再求和，即可得到m次询问中，原数组的所询问区间中的数的和sum0。
4）题目要求和最大，利用排序不等式可知，两数组“顺序”相乘和最大,所以对两数组进行相同的排序操作，然后再求每项相乘再求和的结果，即为所求和最大，记为sum。
5）输出sum-sum0即为所求。
2、时间复杂度
时间复杂度为O(n)
3、代码详解
#include <iostream>
#include <algorithm>
using namespace std;
int A[100010],c[100010];
int main()
{ int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>A[i];
}
int m;
cin>>m;
int L,R;
//差分
for(int i=0;i<m;i++){
cin>>L>>R;
c[L]++;
c[R+1]--;
}
//前缀和
for(int i=1;i<=n;i++){
c[i]+=c[i-1];
}
long long sum0=0,sum=0;
for(int i=1;i<=n;i++){
sum0+=(long long)A[i]*c[i];
}
//排序不等式
sort(A+1,A+n+1);
sort(c+1,c+n+1);
for(int i=1;i<=n;i++){
sum+=(long long)A[i]*c[i];//记得转longlong，否则超int范围
}
cout<<sum-sum0;
return 0;
}
三、知识风暴
1、前缀和与差分
1）前缀和可以用来求指定区间的元素之和，满足Sn=Sn-1+an，即前n项和等于前n-1项和加第n个元素。例如Sk为前k项的前缀和，Sm-1为前m-1项和，则从第m个元素到第k个元素之和为Sk-Sm-1。
2）差分可以用来对指定区间的元素同时加减某任意常数C。具体操作：如果对第m个元素到第k个元素同时加上C，则可以先定义一个差分数组，初识化：差分数组第一个元素与原数组第一个元素相同，对于之后每一个元素都有第i个元素等于原数组第i个元素值-原数组第i-1个元素的值，大小与需要处理的数组大小一致，然后对差分数组的第m个元素加C，第k+1个元素减C，然后再对差分数组求前缀和，所得数组就是所需的结果。（输入原数组时，建议从下标1开始输入，处理差分数组时比较方便直接c[m]+=c,c[k+1]-=c）
注：差分数组是前缀和的逆运算。
2、排序不等式
直接上结论：两个等长数列每项相乘再相加的和，“顺序”相乘（大数乘大数、次大乘次大、直到最小乘最小）该和最大，“逆序”相乘（最大乘最小、次大乘次小、...）该和最小，其他情况位于两者之间。
