由于差分这个知识点经常会被本人忘记，可能是做的题目太少了没怎么碰到。。。因此记录一道贪心加上差分的题目。
本题为第十三届蓝桥杯省赛C++C组题目：4655. 重新排序
具体思路为两部分，贪心+差分。
首先是贪心部分，我们想让新的查询结果尽可能的大，定义一个查询次数数组\(c\),已知在多次查询中，最后每个数总共被查询的次数为\(c_i\)，这样我们可以让大的数匹配多的查询次数。我们可以首先求得当前数组的查询总和sum，然后对数组和查询次数数组分别从小到大排序然后进行点乘即可。
现在的问题就转化为如何求得查询次数数组？
这时候就轮到差分，我们可以定义一个差分数组\(b\)，那么如果说在l-r的区间内进行查询，只需要让\(b[l] + 1, b[r + 1] - 1\)即可，然后最后求一个\(b\)数组的前缀和，就可以得到查询次数数组\(c\)。
具体代码如下：
#include<bits/stdc++.h>
#define xx first
#define yy second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 10;
int n, m;
int a[N], b[N];
int main()
{
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
cin >> m;
while (m--)
{
int l, r;
cin >> l >> r;
b[l]++, b[r + 1]--;
}
ll sum = 0, nsum = 0;
for (int i = 1; i <= n; ++i)
{
b[i] += b[i - 1];
sum += (ll) a[i] * b[i];
}
sort(a + 1, a + n + 1);
sort(b + 1, b + n + 1);
for (int i = 1; i <= n; ++i)
{
nsum += (ll) a[i] * b[i];
}
cout << nsum - sum << endl;
return 0;
}