Description
给定长度为n的序列：a1,a2,…,an，记为a[1:n]。类似地，a[l:r]（1≤l≤r≤N）是指序列：al,al+1,…,ar-1,ar。若1≤l≤s≤t≤r≤n，则称a[s:t]是a[l:r]的子序列。现在有q个询问，每个询问给定两个数l和r，1≤l≤r≤n，求a[l:r]的不同子序列的最小值之和。例如，给定序列5,2,4,1,3，询问给定的两个数为1和3，那么a[1:3]有6个子序列a[1:1],a[2:2],a[3:3],a[1:2],a[2:3],a[1:3]，这6个子序列的最小值之和为5+2+4+2+2+2=17。
Input
输入文件的第一行包含两个整数n和q，分别代表序列长度和询问数。接下来一行，包含n个整数，以空格隔开
,第i个整数为ai，即序列第i个元素的值。接下来q行，每行包含两个整数l和r，代表一次询问。
Output
对于每次询问，输出一行，代表询问的答案。
Sample Input
5 5
5 2 4 1 3
1 5
1 3
2 4
3 5
2 5
Sample Output
28
17
11
11
17
HINT
1 ≤N,Q ≤ 100000,|Ai| ≤ 10^9
Solution
考虑序列中的某个数 Ai ，记它左边第一个比他小的数的位置为 lasti （如果没有就是0），记它右边第一个比他小的数的位置为 nexti （如果没有就是n+1）。我们可以知道该数有贡献的区间左端点范围为 [lasti+1,i] ，右端点范围为 [i,nexti?1] 。所以我们可以把一个数有贡献的范围看做平面上一个矩形，这个平面的横坐标代表的是某个区间左端点，纵坐标代表的是某个区间的右端点，即平面上的点(L,R)代表的是区间[L,R]。所以对于 Ai 来说，它的贡献范围在平面上就是横坐标在 [lasti+1,i] ，纵坐标在 [i,nexti?1] 范围内的矩形区域。同时对于一个询问[L,R]，它所询问的就是横坐标大于L、纵坐标小于R的矩形区域（我们默认平面上R>L的区域贡献是0）。于是问题被我们转换成了平面矩形加法、平面矩形查询权值和的问题。这个可以离线+扫描线用树状数组/线段树在 O(nlog2n) 的时间内完成。
对于平面矩形加法、平面矩形查询权值和的问题，我们按y从小到大扫。
设当前扫描线高度为H，矩形上界为up，矩形下界为down，左边为L，右边为R，当前矩形权值为val。
如果当前矩形还没有扫到上界，那么他在横坐标[L,R]范围内每个点的贡献为 (H?down)?val=H?val?down?val ，我们用两个树状数组/线段树分别维护横坐标上的 val 和 down?val ，查询的时候一个乘一个加，是 k?H+b 的形式，即第一个树状数组中维护每个横纵标对于当前H的k值，第二个则维护b值。
如果当前矩形扫到了上界，即将退出，那么他将来在横坐标[L,R]范围内每个点的贡献为 (up?down)?val ，由于这个贡献不会再变化，所以我们可以把这个贡献加到第二个树状数组/线段树中维护，同时删除第一个线段树中的val即可。
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;template<typename T>inline void read(T &x){T f=1;char ch=getchar();for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(x=0;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';x*=f;
}typedef long long LL;
const int maxn=100010;
int n,m,a[maxn],L[maxn],R[maxn],cnt,sta[maxn],top;
LL ans[maxn];
struct Line{int l,r,y,f,id;bool operator<(Line b)const{if(y==b.y)return f<b.f;return y<b.y;}
}q[maxn<<2];
struct Bit{LL a[maxn],b[maxn];Bit(){memset(a,0,sizeof a);memset(b,0,sizeof b);}void Add(int x,LL val){for(int i=x;i<=n;i+=(i&-i))a[i]+=val,b[i]+=val*x;}void Add(int l,int r,LL val){Add(l,val);Add(r+1,-val);}LL Query(int x){LL ans=0;for(int i=x;i;i-=(i&-i))ans+=a[i]*(x+1)-b[i];return ans;}LL Query(int l,int r){return Query(r)-Query(l-1);}
}k,b;int main(){read(n);read(m);for(int i=1;i<=n;i++)read(a[i]);for(int i=1;i<=n;i++){while(top&&a[sta[top]]>=a[i])top--;top++;L[sta[top]=i]=sta[top-1];}sta[top=0]=n+1;for(int i=n;i>=1;i--){while(top&&a[sta[top]]>a[i])top--;top++;R[sta[top]=i]=sta[top-1];}for(int i=1;i<=m;i++){read(q[i].l),read(q[i].y);q[i].r=q[i].l;q[i].f=1;q[i].id=i;}cnt=m;for(int i=1;i<=n;i++){q[++cnt].l=L[i]+1;q[cnt].f=0;q[cnt].r=i;q[cnt].y=i;q[cnt].id=i;q[++cnt].l=L[i]+1;q[cnt].f=2;q[cnt].r=i;q[cnt].y=R[i]-1;q[cnt].id=i;}sort(q+1,q+cnt+1);for(int i=1;i<=cnt;i++){if(!q[i].f){k.Add(q[i].l,q[i].r,a[q[i].id]);b.Add(q[i].l,q[i].r,(LL)a[q[i].id]*(1-q[i].id));}else if(q[i].f==2){k.Add(q[i].l,q[i].r,-a[q[i].id]);b.Add(q[i].l,q[i].r,(LL)a[q[i].id]*q[i].y);}else ans[q[i].id]=k.Query(q[i].l,n)*q[i].y+b.Query(q[i].l,n);}for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);return 0;
}