序列

Time Limit: 20 Sec Memory Limit: 512 MB

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

img

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include<bits/stdc++.h>
using namespace std;
typedef long long s64;

const int ONE = 100005;
const int INF = 2147483640;

int n,m;
int block[ONE],Q;
int a[ONE],pL[ONE],pR[ONE];
int stk[ONE],top;
int Log[ONE],Bin[ONE],MinD[ONE][19],NumD[ONE][19];
s64 Fl[ONE],Fr[ONE];
s64 ans,Ans[ONE];

struct power
{
    int id;
    int l,r;
}oper[ONE];

inline bool cmp(const power &a,const power &b)
{
    if(block[a.l] != block[b.l]) return block[a.l] < block[b.l];
    return a.r < b.r;
}

inline int get()
{
    int res=1,Q=1;  char c;
    while( (c=getchar())<48 || c>57)
        if(c=='-')Q=-1;
    if(Q) res=c-48;
    while((c=getchar())>=48 && c<=57)
        res=res*10+c-48;
    return res*Q;
}

inline void Pre_Rmq()
{
    Log[0]=-1;  for(int i=1;i<=n;i++) Log[i] = Log[i>>1] + 1;
    Bin[0]=1;   for(int i=1;i<=17; i++) Bin[i] = Bin[i-1] << 1;

    for(int j=1;j<=17;j++)
        for(int i=1;i<=n;i++)
            if(i+Bin[j]-1 <= n)
            {
                int Next = i + Bin[j-1];
                if(MinD[i][j-1] < MinD[Next][j-1])
                    MinD[i][j] = MinD[i][j-1], NumD[i][j] = NumD[i][j-1];
                else
                    MinD[i][j] = MinD[Next][j-1], NumD[i][j] = NumD[Next][j-1];
            }
    else break;
}

inline int Get(int x,int y)
{
    int T = Log[y - x +1];
    if(MinD[x][T] < MinD[y-Bin[T]+1][T]) return NumD[x][T];
    return NumD[y-Bin[T]+1][T];
}

inline void MakepL()
{
    top = 0;
    for(int i=n;i>=1;i--)
    {
        while(top && a[stk[top]] > a[i])
            pL[stk[top--]] = i;
        stk[++top] = i;
    }
    while(top) pL[stk[top--]] = 0;
    for(int i=1;i<=n;i++) pL[i]++;
}

inline void MakepR()
{
    top = 0;
    for(int i=1;i<=n;i++)
    {
        while(top && a[stk[top]] > a[i])
            pR[stk[top--]] = i;
        stk[++top] = i;
    }
    while(top) pR[stk[top--]] = n+1;
    for(int i=1;i<=n;i++) pR[i]--;
}

inline s64 DealL(int l,int r)
{
    int pos = Get(l,r);
    return (s64)a[pos] * (r-pos+1) + Fr[l] - Fr[pos];
}

inline s64 DealR(int l,int r)
{
    int pos = Get(l,r);
    return (s64)a[pos] * (pos-l+1) + Fl[r] - Fl[pos];
}

int main()
{
    n = get();    m = get();    Q = sqrt(n);
    for(int i=1;i<=n;i++)
    {
        a[i] = get(); block[i] = (i-1)/Q+1;
        MinD[i][0] = a[i]; NumD[i][0] = i;
    }

    Pre_Rmq();    MakepL();    MakepR();
    for(int i=1;i<=n;i++) Fl[i] = Fl[pL[i]-1] + (s64)(i-pL[i]+1) * a[i];
    for(int i=n;i>=1;i--) Fr[i] = Fr[pR[i]+1] + (s64)(pR[i]-i+1) * a[i];


    for(int i=1;i<=m;i++)
    {
        oper[i].id = i;
        oper[i].l = get();    oper[i].r = get();
    }
    sort(oper+1, oper+m+1, cmp);

    int l = 1, r = 0;
    for(int i=1;i<=m;i++)
    {
        while(r < oper[i].r) ans += DealR(l,++r);
        while(oper[i].l < l) ans += DealL(--l,r);
        while(r > oper[i].r) ans -= DealR(l,r--);
        while(oper[i].l > l) ans -= DealL(l++,r);

        Ans[oper[i].id] = ans;
    }

    for(int i=1;i<=m;i++)
        printf("%lld\n",Ans[i]);
}