rt。

TLE on #2 #8 #9 #10。

代码如下：

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const LL N = 1e5 + 10, INF = 1e9 + 5;

int n, q;
int a[N];
int stk[N], lmn[N], rmn[N];
LL lsum[N], rsum[N];
int f[N][25];
int id[N];
struct node
{
    int l, r;
    int qid;
    
    bool operator < (const node &W) const
    {
        if (id[l] != id[W.l]) return l < W.l;
		return (id[l] & 1) ? r < W.r : r > W.r;
    }
}qu[N];
LL res[N];

inline void init_ddstk()
{
    a[0] = a[n + 1] = -INF;
    int tt = 0;
    stk[ ++ tt] = 0;
	for (int i = 1; i <= n; ++ i)
	{
		while (tt && a[stk[tt]] >= a[i]) tt -- ;
		lmn[i] = stk[tt], stk[ ++ tt] = i;
	}
	tt = 0;
	stk[ ++ tt] = n + 1;
	for (int i = n; i; -- i)
	{
		while (tt && a[stk[tt]] >= a[i]) tt -- ;
		rmn[i] = stk[tt], stk[ ++ tt] = i;
	}
	for (int i = 1; i <= n; ++ i) lsum[i] = lsum[lmn[i]] + (LL)(i - lmn[i]) * a[i];
	for (int i = n; i; -- i) rsum[i] = rsum[rmn[i]] + (LL)(rmn[i] - i) * a[i];
	a[0] = a[n + 1] = 0;
}

inline int minn(int p, int q) {return a[p] < a[q] ? p : q;}

inline void init_st()
{
    for (int i = 1; i <= n; ++ i) f[i][0] = i;
    int t = log(n) / log(2) + 1;
    for (int j = 1; j < t; ++ j)
        for (int i = 1; i <= n - (1 << j) + 1; ++ i)
            f[i][j] = minn(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}

inline int query_mn(int l, int r)
{
    int t = log(r - l + 1) / log(2);
    return minn(f[l][t], f[r - (1 << t) + 1][t]);
}

inline void init_kuai()
{
    sort(qu + 1, qu + 1 + q);
    int t = sqrt(n);
    for (int i = 1; i <= n; ++ i) id[i] = (i - 1) / t + 1;
}

inline LL getl(int l, int r)
{
    int id = query_mn(l, r);
    return rsum[l] - rsum[id] + (LL)(r - id + 1) * a[id];
}

inline LL getr(int l, int r)
{
    int id = query_mn(l, r);
    return lsum[r] - lsum[id] + (LL)(id - l + 1) * a[id];
}

int main()
{
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; ++ i) scanf("%d", &a[i]);
    for (int i = 1; i <= q; ++ i)
    {
        scanf("%d%d", &qu[i].l, &qu[i].r);
        qu[i].qid = i;
    }
    init_ddstk(), init_st(), init_kuai();
    int l = 1, r = 0;
    LL sum = 0;
    for (int i = 1; i <= q; ++ i)
    {
        while (l > qu[i].l) sum += getl( -- l, r);
        while (r < qu[i].r) sum += getr(l, ++ r);
        while (l < qu[i].l) sum -= getl(l ++ , r);
        while (r > qu[i].r) sum -= getr(l, r -- );
        res[qu[i].qid] = sum;
    }
    for (int i = 1; i <= q; ++ i) printf("%lld\n", res[i]);
    return 0;
}