题目描述
天才程序员菜哭武和石头组队参加一个叫做国际排列计算竞赛 (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] 不是排列。

输入描述:
第一行输入两个数 n (1≤n≤2×105) 和 m (1≤m≤2×105) 。
接下来 m 行，每行输入两个数 l 和 r ，代表这次查询排列中第 l 个到第 r 个的和。

输出描述:
输出一个整数，代表他们队伍总分的最大值。

示例1
输入
7 3
1 3
3 7
5 6

输出
46

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

这个题目思路很简单，查询m次区间，找到被选中最多次数，从大往小排列后，由n到n–不断相乘相加，即可得到结果，问题在于，如何最快得到结果。
以下给出两种解题思路：

解题一：线段树（模板）

#include<iostream>
#include<cstdio>
#include<list>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
using namespace std
typedef long long ll
const int N = 500005
ll n, m, x, y, k, opt, a[N], add[4 * N], sum[4 * N], p[4*N]//add[i]表示第i个区间内每个数要加的值，也就是懒标记(延迟标记)
void build(ll i, ll l, ll r)//建树
{
    if (l == r)
    {
        sum[i] = a[l]
        return
    }
    ll mid = l + r >> 1
    build(2 * i, l, mid)
    build(2 * i + 1, mid + 1, r)
    sum[i] = sum[2 * i] + sum[2 * i + 1]
}
void Add(ll i, ll l, ll r, ll k)//[l,r]区间内每个数加k
{
    add[i] = add[i] + k//add[i]表示第i个区间内每个数要加的值
    sum[i] = sum[i] + (r - l + 1) * k
}
void pushdown(ll i, ll l, ll r, ll mid)//下传标记到左右子区间
{
    if (add[i] == 0)return//没有标记，直接返回
    Add(2 * i, l, mid, add[i])
    Add(2 * i + 1, mid + 1, r, add[i])
    add[i] = 0//清除标记
}
void update(ll i, ll l, ll r, ll x, ll y, ll k)//更新[x,y]区间，将[x,y]区间内每个数加k
{
    if (l > y || r < x)return
    if (l >= x && r <= y)return Add(i, l, r, k)
    ll mid = l + r >> 1
    pushdown(i, l, r, mid)//下传标记后更新左右子区间
    update(2 * i, l, mid, x, y, k)//更新左子区间
    update(2 * i + 1, mid + 1, r, x, y, k)//更新右子区间
    sum[i] = sum[2 * i] + sum[2 * i + 1]
}
ll query(ll i, ll l, ll r, ll x, ll y)//查询[x,y]区间和
{
    if (l > y || r < x)return 0
    if (l >= x && r <= y)return sum[i]
    ll mid = l + r >> 1
    pushdown(i, l, r, mid)//下传标记后查询左右子区间
    return query(2 * i, l, mid, x, y) + query(2 * i + 1, mid + 1, r, x, y)//查询左右子区间之和
}
int cmp(int a, int b)
{
    return a > b
}
int main()
{
    ios::sync_with_stdio(false)
    cin >> n >> m
    for (ll i = 1i <= ni++)
        a[i]=0
    build(1, 1, n)
    while (m--)
    {
        cin >> x >> y 
        update(1, 1, n, x, y, 1)
    }
    for (int i = 1i <= ni++)
       p[i]=query(1, 1, n, i, i)
    sort(p, p + n + 2, cmp)
    ll cnt = 0
    for (int i = 0p[i] != 0i++, n--)
    {
        cnt = cnt + p[i] * n
    }
    printf("%lldn", cnt)
    return 0
}

题解二：差分数组记录（来源于一个小姐姐的代码）

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string>
#include<math.h>
#include<string.h>
#include<bits/stdc++.h>
typedef long long int ll
using namespace std
ll cf[200005],num[200005]
bool cmp(int x,int y)
{
    return x>y
}
int main()
{
    int n,m
    ll sum = 0
    cin>>n>>m
    memset(cf,0,sizeof(cf))
    while(m--)
    {
        int x,y
        cin>>x>>y
        cf[x-1]++cf[y]--
    }
    for(int i=1i<ni++)
    {
        cf[i] = cf[i] + cf[i-1]
    }
    sort(cf,cf+n,cmp)
    for(int i=0i<ni++)
        sum += cf[i] * (n-i)
    cout<<sum<<endl
    return 0
}