P3246 [HNOI2016] Sequence

Given a sequence of length $n$: $a_1, a_2, \cdots, a_n$, denoted by $a[1 \colon n]$. Similarly, $a[l \colon r]$ ($1 \leq l \leq r \leq n$) denotes the sequence $a_l, a_{l+1}, \cdots, a_{r-1}, a_r$. If $1 \leq l \leq s \leq t \leq r \leq n$, then $a[s \colon t]$ is called a subarray of $a[l \colon r]$. Now there are $q$ queries. Each query gives two numbers $l$ and $r$, where $1 \leq l \leq r \leq n$. For each query, find the sum of the minimum values over all subarrays of $a[l \colon r]$. For example, given the sequence $5, 2, 4, 1, 3$ and the query $l = 1$, $r = 3$, the subarrays of $a[1 \colon 3]$ are $a[1 \colon 1], a[2 \colon 2], a[3 \colon 3], a[1 \colon 2], a[2 \colon 3], a[1 \colon 3]$. The sum of their minimum values is $5 + 2 + 4 + 2 + 2 + 2 = 17$.

The first line contains two integers $n$ and $q$, the sequence length and the number of queries. The second line contains $n$ integers separated by spaces. The $i$-th integer is $a_i$, the value of the $i$-th element of the sequence. Each of the next $q$ lines contains two integers $l$ and $r$, describing a query.

For each query, output one line containing the answer.

Constraints: For $100\%$ of the testdata, $1 \leq n, q \leq 100000$, $|a_i| \leq 10^9$. Translated by ChatGPT 5