Description：

给一个长为 $n$ 的序列， $q$ 次询问某个区间的所有子区间的最小值之和。

$1\leqslant n\leqslant 10^5$

Solution：

根本没有什么思路，直接转述题解。

设询问的区间为 $[l,r]$ ，这个区间最小值的位置是 $p$ ，那么对于所有左端点在 $[l,p]$ ，右端点在 $[p,r]$ 的区间最小值都是 $p$ ，这部分对答案的贡献是 $(p-l+1)\times(r-p+1)\times a[p]$ ，这时还需要统计左右端点都在 $[l,p)$ 或 $(p,r]$ 的答案，设 $F[l][r]$ 表示所有左端点在 $[l,r]$ 右端点在 $r$ 的答案，设 $pre[i]$ 为 $i$ 之前第一个比 $i$ 小的位置，所有以 $[pre[i]+1,r]$ 开头以 $r$ 结尾的最小值都是 $a[r]$ ，因此有 $F[l][r]=F[l][pre[r]]+(r-pre[r])\times a[r]$ ，但是这个状态是 $O(n^2)$ 的，考虑如何优化，发现转移跟 $l$ 没啥关系，考虑去掉一维，只用 $f[i]$ 来表示是否可行，因为 $p$ 是 $[l,r]$ 中最小的数字，所以一定 $\exist x\in(p,r],pre[x]=p$ ，也就是说 $f[r]=a[r]\times (r-pre[r])+a[pre[r]]\times(pre[r]-pre[pre[r]])+\cdots+a[x]\times (x-p)+f[p]$ ，那么 $f[r]-f[p]$ 就是 $F[p+1][r]$ ，那么我们只要把 $f[i]$ 做个前缀和就可以得到 $[p+1,r]$ 中的所有 $f[i]$ 每个都减掉 $f[p]$ 就处理完了右半部分，左半部分同理。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<stack>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 100010

int a[MAXN];

int m;

typedef long long ll;

int pre[MAXN],nxt[MAXN];

ll fl[MAXN],fr[MAXN];

ll sfl[MAXN],sfr[MAXN];

int f[MAXN][20];

int my_log2[MAXN];

int calc(int l,int r)

{

	int len = my_log2[r - l + 1] - 1;

	if(a[f[l][len]] < a[f[r - (1 << len) + 1][len]])return f[l][len];

	else return f[r - (1 << len) + 1][len];

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

	a[0] = a[n + 1] = 0xc0c0c0c0;

	stack<int> s;s.push(0);

	for(int i = 1;i <= n;++i)

	{

		while(a[s.top()] >= a[i])s.pop();

		pre[i] = s.top();

		s.push(i);

	}

	while(!s.empty())s.pop();s.push(n + 1);

	for(int i = n;i >= 1;--i)

	{

		while(a[s.top()] >= a[i])s.pop();

		nxt[i] = s.top();

		s.push(i);

	}

	for(int i = 1;i <= n;++i)fr[i] = fr[pre[i]] + 1ll * (i - pre[i]) * a[i];

	for(int i = n;i >= 1;--i)fl[i] = fl[nxt[i]] + 1ll * (nxt[i] - i) * a[i];

	for(int i = n;i >= 1;--i)sfl[i] = sfl[i + 1] + fl[i];

	for(int i = 1;i <= n;++i)sfr[i] = sfr[i - 1] + fr[i];

	for(int i = 1;i <= n;++i)f[i][0] = i;

	for(int k = 1;k <= 19;++k)

	{

		for(int i = 1;i <= n - (1 << k) + 1;++i)

		{

			if(a[f[i][k - 1]] < a[f[i + (1 << (k - 1))][k - 1]])f[i][k] = f[i][k - 1];

			else f[i][k] = f[i + (1 << (k - 1))][k - 1];

		}

	}

	for(int i = 1;i <= n;++i)my_log2[i] = my_log2[i >> 1] + 1;

	int l,r;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d",&l,&r);

		int p = calc(l,r);

		ll ans1 = sfr[r] - sfr[p] - 1ll * (r - p) * fr[p];

		ll ans2 = sfl[l] - sfl[p] - 1ll * (p - l) * fl[p];

		printf("%lld\n",ans1 + ans2 + 1ll * (r - p + 1) * (p - l + 1) * a[p]);

	}

	return 0;

}