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。
输入文件的第一行包含两个整数n和q，分别代表序列长度和询问数。接下来一行，包含n个整数，以空格隔开,第i个整数为ai，即序列第i个元素的值。接下来q行，每行包含两个整数l和r，代表一次询问。
Output
对于每次询问，输出一行，代表询问的答案。
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
莫队，然后考虑向右移动r时答案的变化，显然答案新增了以r为右端点，l…r-1为左端点的许多区间。
定义left[i]表示i左边第一个小于i的数，定义sl[i]表示从i开始一直向左走走到1的代价（最小值之和）。设区间l…r最小值在p处，那么答案就多了sl[r]-sl[p]+(p-l+1)*val[p]。前面的是从i走到最小值位置的代价，后面是按照最小值走l到p这一段的代价。
left[i]可以用单调栈推出，sl[i]可以用left和l到r的最小值位置推出，最小值位置p可以用RMQ求出。
然后左端点移动也是一样的，用right表示i右边第一个小于i的数，sr表示从i考试向右走到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
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
| #include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int INF = 1009999999;
int getint() {
int r = 0, k = 1; char c = getchar();
for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
return r * k;
}
int stack[100005], tail, n, F[100005][30];
int l2k[100005];
LL A[100005];
void RMQ() {
for (int i = 1; i <= n; ++i) {
F[i][0] = i;
for (int x = i; x; x >>= 1)
++l2k[i];
--l2k[i];
}
for (int k = 1; k <= l2k[n]; ++k) {
int len = 1 << k;
for (int i = 1; i <= n; ++i) {
if (i + len - 1 > n) break;
if (A[F[i][k - 1]] < A[F[i + (len >> 1)][k - 1]])
F[i][k] = F[i][k-1];
else
F[i][k] = F[i+(len>>1)][k-1];
}
}
}
int getmin(int l, int r) {
int len = r - l + 1, k = l2k[len];
if (A[F[l][k]] < A[F[r - (1 << k) + 1][k]])
return F[l][k];
return F[r - (1 << k) + 1][k];
}
int L, R, Q, left[100005], right[100005];
int qx[100005], qy[100005], id[100005];
LL sr[100005], sl[100005];
LL Ans[100005];
const int size = 316;
bool cmp(int x, int y) {
if (qx[x] / size == qx[y] / size)
return qy[x] < qy[y];
return qx[x] / size < qx[y] / size;
}
LL LM() {
int minpos = getmin(L, R);
return A[minpos] * (R - minpos + 1) + sr[L] - sr[minpos];
}
LL RM() {
int minpos = getmin(L, R);
return A[minpos] * (minpos - L + 1) + sl[R] - sl[minpos];
}
int main() {
n = getint(); Q = getint();
for (int i = 1; i <= n; ++i) {
A[i] = getint();
while (tail && A[i] <= A[stack[tail]])
--tail;
left[i] = stack[tail];
stack[++tail] = i;
}
for (int i = 1; i <= n; ++i)
sl[i] = sl[left[i]] + A[i] * (i - left[i]);
tail = 0;
stack[0] = n + 1;
for (int i = n; i; --i) {
while (tail && A[i] <= A[stack[tail]])
--tail;
right[i] = stack[tail];
stack[++tail] = i;
}
for (int i = n; i; --i)
sr[i] = sr[right[i]] + A[i] * (right[i] - i);
RMQ();
for (int i = 1; i <= Q; ++i) {
qx[i] = getint();
qy[i] = getint();
id[i] = i;
}
sort(id + 1, id + Q + 1, cmp);
LL ans = A[1];
L = R = 1;
for (int i = 1; i <= Q; ++i) {
int now = id[i];
while (R < qy[now]) {
++R;
ans += RM();
}
while (L < qx[now]) {
ans -= LM();
++L;
}
while (R > qy[now]) {
ans -= RM();
R--;
}
while (L > qx[now]) {
--L;
ans += LM();
}
Ans[now] = ans;
}
for (int i = 1; i <= Q; ++i)
printf("%lld\n", Ans[i]);
return 0;
}
|