排列中的每个数对答案的贡献是它被查询的次数乘以它自身，因此，要最大化答案，应该在被查询次数较多的位置放置较大的数。
用差分和线段树等方法统计每个位置被查询的次数，对每个位置被查询的次数排序，在较大的位置放置排列中较大的数，再计算答案即可。
时间复杂度为 O(n log n)。

#include <iostream>
#include <vector>
#include <algorithm>
const int maxn = 2e5+7;
using ll = long long;

ll n, m, l, r, cur = 0, res = 0, cnt[2][maxn], ans[maxn];

int main(int argc, char *argv[]) {  
    std::ios::sync_with_stdio(false);
    std::cin.tie(0); 
    std::cin >> n >> m;
    for (int i = 0; i < m; i++) {
        std::cin >> l >> r;
        cnt[0][l]++;
        cnt[1][r]--;
    }
    for (int i = 1; i <= n; i++) {
        cur += cnt[0][i];
        ans[i] = cur;
        cur += cnt[1][i];
    }
    std::sort(ans+1, ans+n+1);
    for (ll i = 1; i <= n; i++) {
        res += i * ans[i];
    }
    std::cout << res << '\n';
}