蓝桥杯备赛-差分-重新排序

问题描述

给定一个数组 AA 和一些查询 Li,RiLi​,Ri​, 求数组中第 LiLi​ 至第 RiRi​ 个元素之和。

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

输入格式

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

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

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

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

输出格式

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

样例输入

5
1 2 3 4 5
2
1 3
2 5

样例输出

4

样例说明

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

评测用例规模与约定

对于 30%30% 的评测用例， n,m≤50n,m≤50;

对于 50%50% 的评测用例, n,m≤500n,m≤500;

对于 70%70% 的评测用例, n,m≤5000n,m≤5000;

对于所有评测用例, 1≤n,m≤105,1≤Ai≤106,1≤Li≤Ri≤1061≤n,m≤105,1≤Ai​≤106,1≤Li​≤Ri​≤106 。

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//计算每个位置的查询次数，查询次数最多的放最大的数字
//注意查询和要用long long
//差分--对于一段区间的操作--先在差分数组上做标记--再利用a[i]=a[i-1]+d[i]---重置a数组
//cha是d的前缀和数组，d是cha的差分数组
int main() {
	int n;
	cin >> n;
	vector<int> a(n + 5, 0);
	vector<int> cha(n + 5, 0);
	vector<int> d(n + 5, 0);
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}//初始化a数组
	int m;
	cin >> m;
	int l, r;
	for (int i = 1; i <= m; i++) {
		cin >> l >> r;
		d[l]++;
		d[r + 1]--;
	}//初始化差分数组
	for (int i = 1; i <= n; i++) {
		cha[i] = cha[i - 1] + d[i];
	}//更新cha数组
	long long sum1 = 0;
	long long sum2 = 0;
	for (int i = 1; i <= n; i++){
		sum1 += (long long)a[i] * cha[i];
//将 sum1 += a[i] * cha[i]; 改为 sum1 += (long long)a[i] * cha[i]; 原因在于数据类型的溢出问题。当 a[i] 和 cha[i] 的值较大时，a[i] * cha[i] 的结果可能会超出 int 类型的表示范围（int 通常是 32 位，范围是 -2^31 到 2^31 - 1）。
	}
	sort(a.begin() + 1, a.begin() + 1 + n);//从大到小
	sort(cha.begin() + 1, cha.begin() + 1 + n);
	for (int i = 1; i <= n; i++) {
		sum2 += (long long)a[i] * cha[i];
	}
	cout << sum2 - sum1;
	return 0;
}

 前缀和与差分 图文并茂 超详细整理（全网最通俗易懂）-CSDN博客