个人信息

蓝桥杯笔记：蓝桥杯备赛笔记
知乎：蓝桥杯python组备赛指南
CSDN主页：蓝桥杯python组备赛指南

思路

贪心+前缀和

• 看到区间操作，首先想到前缀和，这样一段区间的操作变为两个点的操作
• 想要最终的结果最大，那就把最大的数字 放在 查询次数最多的位置

python代码

n=int(input())
data=list(map(int,input().split()))
diff=[0]*(n+2)
sum1=[0]*(n+2)
m=int(input())
old=0#原来查询的结果之和
new=0#新查询的结果之和
for i in range(1,n+1):
    sum1[i]=sum1[i-1]+data[i-1]
for _ in range(m):
    l,r=map(int,input().split())
    diff[l]+=1
    diff[r+1]-=1
    old+=sum1[r]-sum1[l-1]
for i in range(1,n+1):
    diff[i]+=diff[i-1]
data.sort(reverse=True)
diff.sort(reverse=True)

for i in range(n):
    new+=diff[i]*data[i]
print(new-old)