Statement

给定长度为 nn 的序列 aia_i，qq 次询问，每次询问给定 l,rl,r，求 a[l:r]a[l:r] 的所有非空子串的最小值之和。

数据范围：n,q≤105n,q\le10^5，∣ai∣≤109|a_i|\le10^9。

Solution

一个询问 l,rl,r 的答案 ans(l,r)=ans(l,x−1)+ans(x+1,r)+ax⋅(x−l+1)⋅(r−x+1)\text{ans}(l,r)=\text{ans}(l,x-1)+\text{ans}(x+1,r)+a_x\cdot(x-l+1)\cdot(r-x+1)。其中 xx 是 l,rl,r 中最小值元素的下标。

ans(l,x−1)\text{ans}(l,x-1) 和 ans(x+1,r)\text{ans}(x+1,r) 本质相同，现考虑求后者。

如果记 fi=[1,i]+[2,i]+⋯+[i,i]f_i=[1,i]+[2,i]+\cdots+[i,i]（[u,v][u,v] 表示 min⁡i=uv{ai}\min_{i=u}^v\{a_i\}），那么 ans(x+1,r)=∑i=x+1rfi−fx\text{ans}(x+1,r)=\sum_{i=x+1}^r f_i-f_x。因为 [1,i]+[2,i]+⋯+[x,i]=[1,x]+[2,x]+⋯+[x,x][1,i]+[2,i]+\cdots+[x,i]=[1,x]+[2,x]+\cdots+[x,x]。

而 fi=fprei+ai⋅(i−prei)f_i=f_{\text{pre}_i}+a_i\cdot(i-\text{pre}_i)，其中 prei\text{pre}_i 为 <i<i 的最大的 jj 满足 aj<aia_j<a_i。单调栈即可。

时间复杂度 O(nlog⁡n)O(n\log n)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
typedef long long LL;
const int N = 1e5 + 3, LogN = 19;
int n, q, a[N], pre[N], nxt[N];
LL pref[N], pres[N], nxtf[N], nxts[N];
namespace ST_Chart {
int f[N][LogN], lg2[N];
void init() {
    lg2[0] = -1;
    for (int i = 1; i <= n; i++) f[i][0] = i, lg2[i] = lg2[i >> 1] + 1;
    for (int i = 1; i <= lg2[n]; i++)
        for (int l = 1; l + (1 << i) - 1 <= n; l++)
            if (a[f[l][i - 1]] < a[f[l + (1 << (i - 1))][i - 1]])
                f[l][i] = f[l][i - 1];
            else
                f[l][i] = f[l + (1 << (i - 1))][i - 1];
}
int query(int l, int r) {
    int len = lg2[r - l + 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];
}
}  // namespace ST_Chart
int main() {
    scanf("%d%d", &n, &q), a[0] = a[n + 1] = INT_MIN;
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    ST_Chart::init();
    for (int i = 1; i <= n; i++) {
        static int stk[N], pstk = 0;
        while (pstk && a[stk[pstk]] >= a[i]) pstk--;
        pre[i] = stk[pstk], stk[++pstk] = i;
        pref[i] = pref[pre[i]] + (LL)a[i] * (i - pre[i]);
        pres[i] = pres[i - 1] + pref[i];
    }
    for (int i = n; i; i--) {
        static int stk[N], pstk = 0;
        stk[0] = n + 1;
        while (pstk && a[stk[pstk]] >= a[i]) pstk--;
        nxt[i] = stk[pstk], stk[++pstk] = i;
        nxtf[i] = nxtf[nxt[i]] + (LL)a[i] * (nxt[i] - i);
        nxts[i] = nxts[i + 1] + nxtf[i];
    }
    for (int l, r, x; q--;) {
        scanf("%d%d", &l, &r), x = ST_Chart::query(l, r);
        LL lef = nxts[l] - nxts[x] - nxtf[x] * (x - l);
        LL rig = pres[r] - pres[x] - pref[x] * (r - x);
        LL mid = (LL)a[x] * (x - l + 1) * (r - x + 1);
        printf("%lld\n", lef + rig + mid);
    }
    return 0;
}