题面
题解
设\([l, r]\)的最小值的位置为\(p\)，那么对于左端点在区间\([l, p]\)，右端点在区间\([p, r]\)的区间最小值都为\(a[p]\)。
这一部分的贡献就是\(a[p] \times (p - l + 1) \times (r - p + 1)\)
设\(f_i = f_{\mathrm{pre}_i} + a_i \times (i - \mathrm{pre}_i)\)，于是我们可以发现\(f_{r + 1} - f_p\)就是以\(r + 1\)为右端点，左端点为\([p + 1, r + 1]\)的答案。
但是我们这里要考虑左端点为\((p, x]\)，右端点为\([x, r]\)的全部答案。
对于点\(r\)，所有以\(r\)为右端点，左端点在\((p, r]\)的答案为\(f_r - f_p\)。
对于点\(r - 1\)，所有以\(r - 1\)为右端点，左端点在\((p, r - 1]\)的答案为\(f_{r - 1} - f_p\)
\(\cdots\)
对于点\(p + 1\)，所有以\(p + 1\)为右端点，左端点在\((p, p + 1]\)的区间答案为\(f_{p + 1} - f_p\)
求个和，就是\((\sum_{i = p + 1} ^ r f_i) - f_p \times(r - p)\)。
设\(g_i = \sum_{j = 1} ^ i f_j\)，那么答案就是\(g_r - g_p - f_p \times (r - p)\)。
同样\(p\)左边的情况是类似的。
时间复杂度\(\mathrm{O}(n\log_2 n)\)
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#define RG register
#define clear(x, y) memset(x, y, sizeof(x))
namespace IO
{
const int BUFSIZE = 1 << 20;
char ibuf[BUFSIZE], *is = ibuf, *it = ibuf;
inline char getchar() { if (is == it) it = (is = ibuf) + fread(ibuf, 1, BUFSIZE, stdin); return *is++; }
}
inline int read()
{
int data = 0, w = 1;
char ch = IO::getchar();
while(ch != '-' && (ch < '0' || ch > '9')) ch = IO::getchar();
if(ch == '-') w = -1, ch = IO::getchar();
while(ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = IO::getchar();
return data * w;
}
const int maxn(1e5 + 10), INF(0x3f3f3f3f), LogN(17);
int n, m, f[LogN][maxn], a[maxn], pre[maxn], suc[maxn];
long long fl[maxn], fr[maxn], gl[maxn], gr[maxn];
int Log[maxn], stk[maxn], top;
inline int min(int x, int y) { return a[x] < a[y] ? x : y; }
inline int query(int l, int r)
{
int k = Log[r - l + 1];
return min(f[k][l], f[k][r - (1 << k) + 1]);
}
int main()
{
n = read(), m = read(); a[0] = a[n + 1] = INF, Log[0] = -1;
for(RG int i = 1; i <= n; i++)
a[f[0][i] = i] = read(), Log[i] = Log[i >> 1] + 1;
for(RG int i = 1; i <= Log[n]; i++)
for(RG int j = 1; j <= n - (1 << (i - 1)) + 1; j++)
f[i][j] = min(f[i - 1][j], f[i - 1][j + (1 << (i - 1))]);
for(RG int i = 1; i <= n; i++)
{
while(top && a[stk[top]] > a[i]) suc[stk[top--]] = i;
pre[i] = stk[top], stk[++top] = i;
}
while(top) pre[stk[top]] = stk[top - 1], suc[stk[top--]] = n + 1;
for(RG int i = 1; i <= n; i++)
fr[i] = 1ll * a[i] * (i - pre[i]) + fr[pre[i]],
gr[i] = gr[i - 1] + fr[i];
for(RG int i = n; i; i--)
fl[i] = 1ll * a[i] * (suc[i] - i) + fl[suc[i]],
gl[i] = gl[i + 1] + fl[i];
while(m--)
{
int l = read(), r = read(), p = query(l, r);
printf("%lld\n", 1ll * (p - l + 1) * (r - p + 1) * a[p]
+ gr[r] - gr[p] - fr[p] * (r - p)
+ gl[l] - gl[p] - fl[p] * (p - l));
}
return 0;
}