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

题目背景

题目提供者:朝田诗乃 ![avartar](https://cdn.luogu.com.cn/upload/pic/66100.png)

题目描述

给定一个长度为 $n$ 的序列 $a$。给定 $m$ 个询问,每次询问一个区间中 $[l,r]$ 中所有数的“Abbi 值”之和。 Abbi 值定义为:若 $a_i$ 在询问区间 $[l,r]$ 中是第 $k$ 小,那么它的“Abbi 值”等于 $k \times a_i$。 为了消除歧义举个例子: 有序列 $\{1,2,2,3\}$,那么 $1$ 是第 $1$ 小,$2$ 是第 $2$ 小,$3$ 是第 $4$ 小,序列 Abbi 值和为: $$1 \times 1+2 \times 2+2 \times 2+3 \times 4=21.$$

输入格式

输出格式

说明/提示

前 2 个数据点,$1≤n,m≤1000$,时限 1s。 接下来 14 个数据点,$1≤n,a_i,m≤100000$,$1≤l≤r≤n$,时限 1s。 最后两个数据点,$1≤a_i≤100000$,$1≤l≤r≤n$,$1≤n,m≤500000$,时限 3s。 建议使用读入优化。建议开启 O2 优化。 数据已经过加强。