题目大意
通过修改序列 \(a\) 中的数的顺序，使
\[\sum_{i=1}^q\sum_{j=l}^ra[j]
\]
最大，并输出它的值。
思路
一道简单贪心 \(+\) 差分，通过差分的优秀的 \(O(1)\) 区间修改能力帮助我们求出每个位置在询问中询问的次数，进行排序，最后次数较多的就让值较大的数来，以此类推。
AC Code
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+10;
long long n,q,a[MAXN],b[MAXN],s[MAXN];
long long sum;
template <typename T> inline void read(T &in) {
in=0;int fh=1;char ch=getchar();
while(!isdigit(ch)) {
if(ch=='-') fh=-1;
ch=getchar();
}
while(isdigit(ch)) in=(in<<1)+(in<<3)+(ch^48),ch=getchar();
in*=fh;
}
template <typename T,typename... Ts> inline void read(T &in,Ts&... ins) {read(in),read(ins...);}
template <typename T> inline void write(T out) {
static char str[20];int top=0;
if(out<0) putchar('-'),out-=2*out;
do{str[++top]=out%10+48,out/=10;} while(out);
while(top) putchar(str[top--]);
putchar('\n');
}
template <typename T,typename... Ts> inline void write(T out,Ts... outs) {write(out),write(outs...);}
int main(){
read(n,q);
for(int i=1;i<=n;i++) read(a[i]);
while(q--){
int l,r;
read(l,r);
b[l]++;
b[r+1]--;
}
for(int i=1;i<=n;i++) s[i]=s[i-1]+b[i];
sort(a+1,a+n+1);
sort(s+1,s+n+1);
for(int i=1;i<=n;i++) sum=sum+(a[i]*s[i]);
cout<<sum;
return 0;
}