1194: 排列计算(差分)

天才程序员菜哭武和石头组队参加一个叫做国际排列计算竞赛 (International Competition of Permutation Calculation, ICPC) 的比赛，这个比赛的规则是这样的： 

一个选手给出一个长度为 n 的排列，另一个选手给出 m 个询问，每次询问是一个形如 (l, r) 的数对，查询队友给出的排列中第 l 个数到第 r 个数的和，并将查询到的这个区间和加入总分，最后总分最高的队伍就能获胜。

石头手速很快，在比赛一开始就给出了 m 个询问；菜哭武也很强，他总是能找到最合适的排列，使得他们队的总分尽可能高。

在看比赛直播的你看到了石头给出的 m 个询问，聪明的你能不能预测出他们队伍最终的得分呢？ 

一个排列是一个长度为 n 的数列，其中 1 ~ n 中的每个数都在数列中恰好出现一次。比如 [1, 3, 2] 是一个排列，而 [2, 1, 4] 和 [1, 2, 3, 3] 不是排列。 

一个符合条件的排列是 [1, 3, 6, 4, 7, 5, 2]，于是最终的得分为 (1 + 3 + 6) + (6 + 4 + 7 + 5 + 2) + (7 + 5) = 46

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=1e9+7;
const int N=2e5+5;
int d[N];


int main(){
    ios::sync_with_stdio(0);
    ll n,m,sum=0;
    cin>>n>>m;
    while(m--){
        ll a,b;
        cin>>a>>b;
        d[a]++;
        d[b+1]--;
    }
    for(ll i=1;i<=n;i++){
        d[i]+=d[i-1];
        //cout<<d[i]<<endl;
    }
    sort(d+1,d+n+1);
    for(ll i=1;i<=n;i++){
        sum+=d[i]*i;
    }
    cout<<sum<<endl;
    return 0;
}