差分：蓝桥杯2022省赛重新排序

前言

这是一道蓝桥杯2022省赛原题，其差分思想和实现的思路比较灵活，值得尝试和学习。

题目

给定一个数组 A和一些查询 Li,Ri, 求数组中第 Li 至第 Ri 个元素之和。

小蓝觉得这个问题很无聊, 于是他想重新排列一下数组, 使得最终每个查 询结果的和尽可能地大。小蓝想知道相比原数组, 所有查询结果的总和最多可 以增加多少?

输入格式

输入第一行包含一个整数 n。

第二行包含 n 个整数 A1,A2,⋯,An, 相邻两个整数之间用一个空格分隔。

第三行包含一个整数 m 表示查询的数目。

接下来 m 行, 每行包含两个整数 Li、Ri, 相邻两个整数之间用一个空格分 隔。

输出格式

输出一行包含一个整数表示答案。

样例输入

1
2
3
4
5
5
1 2 3 4 5
2
1 3
2 5

样例输出

1
4

样例说明

原来的和为 6+14=20, 重新排列为 (1,4,5,2,3) 后和为 10+14=24, 增加了 4。

官方题解

题目希望所有查询之和经过重新排序后增加最多，因此考虑先计算出当前的查询之和，以及排序后最大的查询之和。

由于给定查询区间，因此排序前和排序后询问的区间是一样的，那么可以利用 m 个查询区间计算出每个位置 j 的累计查询次数 s[j]，最终查询总和为
$$
\sum_{j=1}^{n} A_j \cdot s[j]
$$

每次查询区间 [Li,Ri]，相当于区间 [Li,Ri] 中的每个数字查询次数 +1+1。为了统计每个数字的查询次数，需要实现区间加法，可以使用线段树、树状数组、差分数组来得到数组 ss 的值。

此处使用差分数组的做法实现区间更新：

  • 在区间 [Li,Ri] 上 +1+1，只需要在差分数组 b[Li]++，b[Ri]−−。
  • 最终

$$
s[j] = \sum_{i=1}^{j} b[i]
$$

此时最开始的查询之和相当于统计每个数字的查询次数：
$$
\sum_{j=1}^{n} A_j s[j]
$$

需要对数组 A 进行排序，使得新的 sum 最大。利用贪心的思想可以得出结论：查询次数越多，数值一定越大。这样才能保证和最大。

因此对 A 数组从小到大排序，而 s 数组也从小到大排序，使得A中最小的对应 s 中最小的，A 中最大的对应 s 中最大的，此时可以保证和最大。

个人反思

这题涉及了差分和贪心算法，有以下几个难点要注意：

  • 要把区间维护转换为对数组的单个点的维护，这样就可以直接用数组进行计算，就方便很多。
  • 题目中的查询次数区间的维护操作对应了差分算法，差分计算完后还要记得计算前缀和得到查询次数原数组。
  • 在思考怎么把最大的数对应到查询次数最大的点时，不仅可以把数字排序再通过查询次数的优先级对应上原数组，还可以直接把原数组的查询区间也给排序了，反正是一一对应的关系，不会影响结果。总结就是数据和位置都可以排序，不要被困于模拟操作的局限当中，位置也是可以排序的。
  • 本题的边界问题也是个坑，注意写代码时一定要全部一遍考虑好，不然后期debug很麻烦。

AC_Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;

int a[maxn], b[maxn], s[maxn];
int main()
{
    //输入
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    int m;
    cin >> m;
    for(int i = 1; i <= m; i++)
    {
        int l, r;
        cin >> l >> r;
        //差分数组实现区间加法更新
        b[l]++, b[r + 1]--;
    }
    //对差分数组求前缀和，得到每个数字的查询次数
    for(int i = 1; i <= n; i++)
        s[i] = s[i - 1] + b[i];
    ll sum1 = 0, sum2 = 0;
    //sum1为原始和
    for(int i = 1; i <= n; i++)
        sum1 += (ll)a[i] * s[i];
    sort(a + 1, a + 1 + n);
    sort(s + 1, s + 1 + n);;
    //sum2为贪心后的最大和
    for(int i = 1; i <= n; i++)
        sum2 += (ll)a[i] * s[i];
    cout<<sum2 - sum1<<endl;
    return 0;
}