loj #2051. 「HNOI2016」序列

#2051. 「HNOI2016」序列

题目描述

给定长度为 n nn 的序列：a1,a2,⋯,an a_1, a_2, \cdots , a_na​1​​,a​2​​,⋯,a​n​​，记为 a[1:n] a[1 \colon n]a[1:n]。类似地，a[l:r] a[l \colon r]a[l:r]（1≤l≤r≤N 1 \leq l \leq r \leq N1≤l≤r≤N）是指序列：al,al+1,⋯,ar−1,ar a_{l}, a_{l+1}, \cdots ,a_{r-1}, a_ra​l​​,a​l+1​​,⋯,a​r−1​​,a​r​​。若 1≤l≤s≤t≤r≤n1\leq l \leq s \leq t \leq r \leq n1≤l≤s≤t≤r≤n，则称 a[s:t] a[s \colon t]a[s:t]是 a[l:r] a[l \colon r]a[l:r] 的子序列。

现在有 q qq 个询问，每个询问给定两个数 l ll 和 r rr，1≤l≤r≤n 1 \leq l \leq r \leq n1≤l≤r≤n，求 a[l:r] a[l \colon r]a[l:r] 的不同子序列的最小值之和。例如，给定序列 5,2,4,1,3 5, 2, 4, 1, 35,2,4,1,3，询问给定的两个数为 1 11 和 3 33，那么 a[1:3] a[1 \colon 3]a[1:3] 有 6 66 个子序列 a[1:1],a[2:2],a[3:3],a[1:2],a[2:3],a[1:3]a[1 \colon 1], a[2 \colon 2], a[3 \colon 3], a[1 \colon 2],a[2 \colon 3], a[1 \colon 3]a[1:1],a[2:2],a[3:3],a[1:2],a[2:3],a[1:3]，这 666 个子序列的最小值之和为 5+2+4+2+2+2=175+2+4+2+2+2=175+2+4+2+2+2=17。

输入格式

输入文件的第一行包含两个整数 n nn 和 q qq，分别代表序列长度和询问数。
接下来一行，包含 n nn 个整数，以空格隔开，第 i ii 个整数为 ai a_ia​i​​，即序列第 iii 个元素的值。
接下来 q qq 行，每行包含两个整数 l ll 和 r rr，代表一次询问。

输出格式

对于每次询问，输出一行，代表询问的答案。

样例

样例输入

5 5 
5 2 4 1 3 
1 5 
1 3 
2 4 
3 5 
2 5

样例输出

28 
17 
11 
11 
17

数据范围与提示

对于 100%100\%100% 的数据，1≤n,q≤100000,∣ai∣≤109 1 \leq n,q \leq 100000 ,|a_i| \leq 10^91≤n,q≤100000,∣a​i​​∣≤10​9​​