P5501 [LnOI2019] Welcome All Who Come, Do Not Chase Those Who Leave

Problem provider: Asada Shino 

Given a sequence $a$ of length $n$. There are $m$ queries. For each query, you need to find the sum of the “Abbi value” of all numbers in the interval $[l,r]$. The Abbi value is defined as follows: if $a_i$ is the $k$-th smallest in the query interval $[l,r]$, then its “Abbi value” equals $k \times a_i$. To avoid ambiguity, here is an example: Given the sequence $\{1,2,2,3\}$, then $1$ is the $1$-st smallest, $2$ is the $2$-nd smallest, and $3$ is the $4$-th smallest. The sum of Abbi values of the sequence is: $$1 \times 1+2 \times 2+2 \times 2+3 \times 4=21.$$

The first line contains two integers, $n$ and $m$, representing the length of the sequence and the number of queries. The second line contains $n$ numbers. The $i$-th number is $a_i$, representing the initial value of the sequence. The next $m$ lines each contain two numbers $l$ and $r$, representing a query interval.

For each query, output one line with the answer.

Constraints For the first 2 test points, $1 \le n,m \le 1000$, time limit $1\text{s}$. For the next 14 test points, $1 \le n,a_i,m \le 100000$, $1 \le l \le r \le n$, time limit $1\text{s}$. For the last 2 test points, $1 \le a_i \le 100000$, $1 \le l \le r \le n$, $1 \le n,m \le 500000$, time limit $3\text{s}$. It is recommended to use fast input. It is recommended to enable $O2$ optimization. The testdata has been strengthened. Translated by ChatGPT 5