题目描述

已知长度n的整数序列。有q个询问，查询A[l]..A[r]之和，并统计所有询问的总和。

现在请你来重新排列序列中的数字，使得这个总和最大。

输入格式

第一行，正整数n,q.(1≤n,q≤ $2*10^5$)

第二行，n个正整数(值不超过$2*10^5$)，表示这个整数序列。

接下来q行，每行两个整数l,r.(1≤l≤r≤n)，表示q个询问。

输出格式

一个整数，表示答案。

样例

输入

in1
3 3
5 3 2
1 2
2 3
1 3
in2
5 3
5 2 4 1 3
1 5
2 3
2 3

输出

out1
25
out2
33

数据范围与提示

样例1： 将序列5,3,2调整为3,5,2

样例2： 将序列5,2,4,1,3调整为3,4,5,1,2

我的代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,chafen[200001],prefix[200001],a[200001];
unsigned long long ans;
int main(){
	scanf("%d%d",&n,&m);
	for(register int i=1;i<=n;i++)scanf("%d",a+i);
	sort(a+1,a+n+1);
	for(register int i=1,a,b;i<=m;i++)
	{
		scanf("%d%d",&a,&b);
		chafen[a]++;
		chafen[b+1]--;
	}
	for(register int i=1;i<=n;i++)prefix[i]=prefix[i-1]+chafen[i];
	sort(prefix+1,prefix+n+1);
	for(register int i=1;i<=n;i++)
	{
//		printf("%d %d\n",a[i],prefix[i]);
		ans+=1ull*prefix[i]*a[i];
	}
	cout<<ans;
}

50pts