排列计算--题解

根据题意可以推出在排列中将出现次数最多的地方放上最大的数，剩下的依次递减。要计算每个位置出现的位置，依据数据范围，暴力模拟会WA，简单差分一下就可以了。
代码如下：

#include<iostream>
#include<algorithm>
using namespace std;
int a[200010];
bool cmp(int a, int b)
{
    return a > b;
}
int main()
{
    int n, m;
    cin >> n >> m;
    while (m--)
    {
        int l, r;
        cin >>l >> r;
        a[l] += 1;
        a[r + 1] -= 1;

    }
    for (int i = 1;i <= n;i++)
        a[i] = a[i - 1] + a[i];
    sort(a + 1, a + 1 + n, cmp);
    long long int ans = 0,i=1;
    while (a[i])
    {
        ans += a[i] * (n + 1 - i);
        i++;
    }
    cout << ans << endl;
    return 0;
}

求牛币，QWQ。