P7882 [Ynoi2006] rsrams

Given a sequence $a_1,\dots,a_n$ of length $n$, you need to process $m$ queries. Each query gives $l, r$, and the answer is: $\sum\limits_{L=l}^r \sum\limits_{R=L}^r \sum\limits_{c=1}^n c\cdot \left[R-L+1

The first line contains two integers $n, m$. The second line contains $n$ integers $a_1,\dots,a_n$. The next $m$ lines each contain two integers $l, r$, representing a query.

Output $m$ lines. Each line contains one integer, representing the answer to each query.

Idea: zjjcth330, Solution: nzhtl1477&ccz181078, Code: ccz181078, Data: ccz181078. Constraints: For $100\%$ of the testdata, $1\le n\le 10^6$, $1\le m\le 10^6$, $1\le a_i\le n$, $1\le l\le r\le n$. Translated by ChatGPT 5