L,r重新排序

问题描述

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

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

输入格式

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

第二行包含 $n$ 个整数 $A_1,A_2,\cdots ,A_n$, 相邻两个整数之间用一个空格分隔。

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

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

输出格式

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

样例输入

5
1 2 3 4 5
2
1 3
2 5

样例输出

4

样例说明

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

评测用例规模与约定

对于 $30$ 的评测用例， $n,m\le 50$;

对于 $50$ 的评测用例, $n,m\le 500$;

对于 $70$ 的评测用例, $n,m\le 5000$;

对于所有评测用例, $1\le n,m\le 10^5,1\le A_i\le 10^6,1\le L_i\le R_i\le 10^6$ 。

解题思路

分析
1、确定内容：
给定查询区间，排序前和排序后询问的区间是一样的，则$m$个查询区间中计算出每个位置$j$的累计查询次数$s[j]$是确定的
2、期望
最大的数值被查询的次数最多
3、查询区间的含义
每次查询区间$[L_i,R_i]$，相当于区间$[L_i,R_i]$中的每个数字查询次数$+1$。为了统计每个数字的查询次数，需要实现区间加法
区间内每个位置被查询一次 $\equiv$ 修改区间+1——差分数组、线段树

差分数组现区间更新：

• 在区间$[L_i,R_i]$上$+1$，只需要在差分数组$b[L_i]++，b[R_i]--$。
• 最终$s[j]={\sum }_{i=1}^{j}b[i]$

查询之和相当于统计每个位置的查询次数:$\times$位置上的数：
$$su{m}_1=\sum _{j=1}^n{A}_{j}s[j]$$
任务需求：需要对数组$A$进行排序，使得新的$sum$最大。
贪心：查询次数越多，数值一定越大。这样才能保证和最大。
方法：对$A$数组和$s$数组从小到大排序（使得$A$中最小的对应$s$中最小的，$A$中最大的对应$s$中最大的）

AC_Code（Python）

# -*- coding: utf-8 -*-
# @Author : BYW-yuwei
# @Software: python3.8.6
#输入
n = int(input())
a = list(map(int, input().split()))
a = [0, *a]
b = [0] * (n + 10)
s = [0] * (n + 1)m = int(input())
for i in range(m):#差分数组实现区间加法更新l, r = map(int, input().split())b[l] += 1b[r + 1] -= 1
#对差分数组求前缀和，得到每个数字的查询次数
for i in range(1, n + 1):s[i] = s[i - 1] + b[i]#sum1为原始和，sum2为贪心后的最大和
sum1, sum2 = 0, 0
for i in range(1, n + 1):sum1 += a[i] * s[i]a.sort()
s.sort()for i in range(1, n + 1):sum2 += a[i] * s[i]
print(sum2 - sum1)