创建个人网站教程,专业网站制作 广州番禺,重庆医院门户网站建设,免费wap自助建站系统问题描述 给定一个数组A和一些查询 L,R求数组中第L至第 R个元素之和。 小蓝觉得这个问题很无聊,于是他想重新排列一下数组使得最终每个查 询结果的和尽可能地大。小蓝想知道相比原数组,所有查询结果的总和最多可 以增加多少? 输入格式 输入第一行包含一个整数n。 第二行包含n个… 问题描述 给定一个数组A和一些查询 L,R求数组中第L至第 R个元素之和。 小蓝觉得这个问题很无聊,于是他想重新排列一下数组使得最终每个查 询结果的和尽可能地大。小蓝想知道相比原数组,所有查询结果的总和最多可 以增加多少? 输入格式 输入第一行包含一个整数n。 第二行包含n个整数A12,··An,相邻两个整数之间用一个空格分隔。 第三行包含一个整数m表示查询的数目。 接下来m行每行包含两个整数 L、R相邻两个整数之间用一个空格分 隔。 输出格式 输出一行包含一个整数表示答案 样例输入 5 1 2 3 4 5
2
1 3
2 5
输出
4 import os
import sys# 请在此输入您的代码
nint(input())
N100003
a[0]*N
d[0]*N #差分数组
cnt[0]*N #差分数组的累计和a[1:n1]map(int,input().split())
mint(input())
ans10
ans20for i in range(m):L,Rmap(int,input().split())d[L]1d[R1]-1cnt[0]d[0]
for i in range(1,n1):cnt[i]cnt[i-1]d[i] #计算累计和每个元素被查询的次数for i in range(1,n1):ans1a[i]*cnt[i] #计算需要查询的元素之和每个元素被查询的次数*元素数值a[1:n1]sorted(a[1:n1]) #排序后用较大的权重*较大的元素
cnt[1:n1]sorted(cnt[1:n1])for i in range(1,n1):ans2a[i]*cnt[i]
print(ans2-ans1) 差分数组详细解释文章什么是差分数组-CSDN博客
