#P5501. [LnOI2019] 来者不拒,去者不追

[LnOI2019] 来者不拒,去者不追

题目背景

题目提供者:朝田诗乃

avartar

题目描述

给定一个长度为nn的序列aa。给定mm个询问,每次询问一个区间中[l,r][l,r]中所有数的“Abbi值”之和

Abbi值定义为:若aia_i在询问区间[l,r][l,r]中是第kk小,那么它的“Abbi值”等于k×aik \times a_i

为了消除歧义举个例子:

有序列1 2 2 3,那么1是第1小,2是第2小,3是第4小,序列Abbi值和为

1×1+2×2+2×2+3×4=211 \times 1+2 \times 2+2 \times 2+3 \times 4=21

输入格式

第一行两个整数,nnmm,分别表示序列长度和询问组数。

第二行nn个数,第ii个数为aia_i,表示序列的初始值。

接下来mm行,每行两个数llrr,表示询问区间。

输出格式

对于每个询问,输出一行表示答案

4 2
1 2 2 3
1 4
1 2
21
5
10 5
8 6 9 8 1 1 3 10 7 9
5 8
1 3
5 7
9 9
5 6

51
49
11
7
2

提示

前2个数据点,1n,m10001≤n,m≤1000,时限1s。

接下来14个数据点,1n,ai,m1000001≤n,a_i,m≤1000001lrn1≤l≤r≤n,时限1s。

最后两个数据点,1ai1000001≤a_i≤1000001lrn1≤l≤r≤n1n,m5000001≤n,m≤500000,时限3s。

建议使用读入优化。建议开启O2优化。

数据已经过加强。