Created time
Jan 5, 2023 09:12 AM
date
status
category
Origin
summary
tags
type
URL
icon
password
slug
差分介绍
差分其实是前缀和的逆运算。给定构造差分数组，使得。
差分的核心操作：将全部加上，等价于。
- 对于a[1~L-1]无影响
- a[L~R]加上了C
- a[R+1~N]无影响
重新排序
给定一个数组 和一些查询 ，求数组中第 至第 个元素之和。这个问题很无聊，重新排列一下数组，使得最终每个查询结果的和尽可能地大。相比原数组，所有查询结果的总和最多可以增加多少?
输入第一行包含一个整数 。第二行包含 个整数 ，相邻两个整数之间用一个空格分隔。第三行包含一个整数 表示查询的数目。接下来 行，每行包含两个整数 ，相邻两个整数之间用一个空格分隔。输出一行包含一个整数表示答案。
对于 的评测用例，；对于 的评测用例，；对于 的评测用例，；对于所有评测用例，。
输入样例：
输出样例：
原来的和为 ，重新排列为后和为 ，增加了 。