练习-依依的询问最小值（前缀和差分）

问题描述

依依有个长度为 n 的序列 a，下标从 1 开始。

她有 m 次查询操作，每次她会查询下标区间在[li​,ri​] 的 a 中元素和。她想知道你可以重新排序序列 a，使得这 m 次查询的总和最小。

求你求出 m 次查询总和的最小值。

输入格式

第一行输入两个整数 n,m，表示序列 a 的长度以及查询次数。

第二行输入 n 个整数 ai​，表示序列 a 中的元素。

接下来 m 行，每行输入两个整数 li,ri（1≤li≤ri≤n），表示询问的下标区间。

输出格式

输出仅一行，包含一个整数，表示 m 次查询总和的最小值。

样例输入

3 2
1 2 3
1 2
2 3

样例输出

7

样例解释

1. 输入

• 序列 a=[1,2,3]a=[1,2,3]。

• 查询区间：

  • [1,2]：a[1]+a[2]

  • [2,3]：a[2]+a[3]

2. 计算每个索引被查询的次数

• 索引 1：被查询区间 [1,2]覆盖，次数为 1。

• 索引 2：被查询区间 [1,2]和 [2,3] 覆盖，次数为 2。

• 索引 3：被查询区间 [2,3]覆盖，次数为 1。

3. 重新排列序列 a

• 将较大的元素分配给被较少查询区间覆盖的索引，将较小的元素分配给被较多查询区间覆盖的索引。

• 索引 2 被查询的次数最多，因此应该分配最小的元素。

• 索引 1 和 3 被查询的次数较少，可以分配较大的元素。

重新排列后的序列：

• 索引 1：3

• 索引 2：1

• 索引 3：2

即 a=[3,1,2]。

4. 计算查询区间的元素和

• [1,2]：a[1]+a[2]=3+1=4

• [2,3]：a[2]+a[3]=1+2=3

5. 总和

• 总和为 4+3=74+3=7。

---

1. 问题分析

• 目标：通过重新排列序列 a，使得所有查询区间的元素和的总和最小。

• 查询区间：每个查询区间 [li,ri] 的元素和是 a[li]+a[li+1]+⋯+a[ri]。

• 操作：只能重新排列序列 a，不能修改或删除元素。

---

2. 关键观察

1. 查询区间的重叠

• 不同的查询区间可能会重叠，导致某些索引被多次查询。

• 例如，查询区间 [1,3]和 [2,4] 重叠在索引 2 和 3。

2. 元素分配的策略

• 如果一个索引被多个查询区间覆盖，那么该索引的值会对多个查询区间的元素和产生影响。

• 为了最小化总和，我们应该将较大的元素分配给被较少查询区间覆盖的索引，将较小的元素分配给被较多查询区间覆盖的索引。

3. 差分数组的使用

• 差分数组可以高效地统计每个索引被查询的次数。

• 通过差分数组，我们可以在 O(n+m) 的时间复杂度内计算出每个索引被查询的次数。

4. 排序和分配

• 将查询次数从小到大排序，将序列 a 从大到小排序。

• 将较大的元素分配给被较少查询区间覆盖的索引，将较小的元素分配给被较多查询区间覆盖的索引。

---

3. 解决思路

基于以上观察，我们可以设计以下解决思路：

1. 统计每个索引被查询的次数：

   • 使用差分数组统计每个索引被查询的次数。

   • 通过前缀和数组计算每个索引被查询的次数。

2. 排序：

   • 将查询次数从小到大排序。

   • 将序列 a 从大到小排序。

3. 分配元素：

   • 将较大的元素分配给被较少查询区间覆盖的索引，将较小的元素分配给被较多查询区间覆盖的索引。

4. 计算最小总和：

   • 计算所有查询区间的元素和的总和。

---

解题代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
int g[N]; // 差分数组，用于统计每个索引被查询的次数
int prefix[N]; // 前缀和数组，用于计算每个索引被查询的次数
int a[N]; // 存储输入的序列 a// 自定义排序函数，用于将数组从大到小排序
bool cmp(int u, int v)
{return u > v;
}int main()
{int n, m; // n 是序列长度，m 是查询次数long long cnt = 0; // 用于存储最小总和cin >> n >> m; // 输入序列长度 n 和查询次数 m// 输入序列 a，索引从 1 开始for (int i = 1; i <= n; i++){cin >> a[i];}// 使用差分数组统计每个索引被查询的次数while (m){int l, r; // 查询区间的左右端点cin >> l >> r;g[l]++; // 从 l 开始，查询次数增加 1g[r + 1]--; // 从 r + 1 开始，查询次数减少 1m--; // 处理完一个查询，m 减 1}// 计算每个索引被查询的次数prefix[1] = g[1]; // 初始化 prefix[1]for (int i = 2; i <= n; i++){prefix[i] = prefix[i - 1] + g[i]; // 计算 prefix[i]}// 将 prefix 数组从小到大排序sort(prefix + 1, prefix + 1 + n);// 将 a 数组从大到小排序sort(a + 1, a + 1 + n, cmp);// 计算最小总和for (int i = 1; i <= n; i++){cnt += a[i] * prefix[i]; // 将较大的元素分配给被较少查询区间覆盖的索引}cout << cnt;return 0;
}