题面
为什么感觉AK IOI比AK ZJOI简单???
首先考虑单次$O(n)$dp
考虑递归树，发现即为笛卡尔树
似乎可以在笛卡尔树上乱搞
然后对于每个询问暴力展开一层
这样询问区间最左端/最右端就必有一个很大的值比区间内h都大
反转后可以只考虑最左端
于是乎对应笛卡尔树上就是$\exists i~ l_i = ql~and~qr \leq r_i$(l,r即为该子树对应区间)
所以我们需要处理出$\forall i~dp[l_i][x](x\in [l_i,r_i]$
考虑从子树合并上来
由于当前处理点即为$mid$
(左子树已处理好)
嗯，这个怎么搞???
展开一下
手玩几组就可以发现决策具有单调性
性感的理解:当右端点向右移动，会议地点向左移显然不优
性理的证明:当右端点向右移动1，第一个柿子增加$h[mid]$，第二个柿子增加不大于$h[mid]$(因为右边均不大于$h[mid]$)
发现需要支持二分，单点赋值，区间加，区间赋值为直线
果断线段树
$O((n + q)logn)$
解题顺序:
1.读入，拆询问
2.搞出st表，建好笛卡尔树
3.$dfs$同时一路向上合并维护答案
4.反转数组再来一次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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
// #define DEBUG fprintf(stderr, "for %d DEBUG:\n\trunning at funtion %s, line %d\n", debugcnt++, __FUNCTION__, __LINE__);
using namespace std;
typedef long long ll;
int debugcnt;
int n, q;
ll ans[3000010];
struct query {
ll c;
ll l, r;
int id;
int nxt;
} ques[1500010];
int ls[750010], rs[750010];
int *qhead;
int tot, cur1[750010], cur2[750010];
inline void addquery(ll c, ll l, ll r, int i, int *head) {
// DEBUG
ques[++tot] = query{c, l, r, i, head[l]};
head[l] = tot;
}
ll tag1[3000010], tag2[3000010], tag3[3000010];//tag1 为 k, tag2 为 b, tag3 为 赋为0操作
//先赋值后修改
ll st[750010][21], h[750010], lg2[7500010];
ll lans[3000010], rans[3000010];
inline int _max1(int a, int b) {
if(h[a] != h[b]) return h[a] > h[b] ? a : b;
return max(a, b);
}
inline int _max2(int a, int b) {
if(h[a] != h[b]) return h[a] > h[b] ? a : b;
return min(a, b);
}
typedef int (*ffmax)(int, int);
ffmax _max;
inline void build_st() {
// DEBUG
for(int i = n; i > 0; i--) {
st[i][0] = i;
for(int j = 1; i + (1 << j) - 1 <= n; j++) st[i][j] = _max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
lg2[0] = -1;
for(int i = 1; i <= n; i++) lg2[i] = lg2[i >> 1] + 1;
}
inline int rmq(int l, int r) {
// DEBUG
int k = lg2[r - l + 1];
return _max(st[l][k], st[r - (1 << k) + 1][k]);
}
inline void _add(int x, int l, int r, ll k, ll b) {
// DEBUG
lans[x] += k * l + b;
rans[x] += k * r + b;
tag1[x] += k;
tag2[x] += b;
}
inline void down(int x, int l, int r) {
// DEBUG
if(tag3[x]) {
tag1[x << 1] = tag1[x << 1 | 1] = 0;
tag2[x << 1] = tag2[x << 1 | 1] = 0;
tag3[x << 1] = tag3[x << 1 | 1] = 1;
lans[x << 1] = lans[x << 1 | 1] = 0;
rans[x << 1] = rans[x << 1 | 1] = 0;
tag3[x] = 0;
}
// DEBUG
if((tag1[x] | tag2[x]) == 0) return;
int mid = l + r >> 1;
_add(x << 1, l, mid, tag1[x], tag2[x]);
_add(x << 1 | 1, mid + 1, r, tag1[x], tag2[x]);
tag1[x] = tag2[x] = 0;
}
inline void up(int x) {
// DEBUG
lans[x] = lans[x << 1];
rans[x] = rans[x << 1 | 1];
}
inline ll get(int x, int l, int r, int k) {
// DEBUG
if(l == r) return lans[x];
down(x, l, r);
int mid = l + r >> 1;
if(k <= mid) return get(x << 1, l, mid, k);
return get(x << 1 | 1, mid + 1, r, k);
}
inline void add(int x, int l, int r, int k, ll b) {
// DEBUG
if(l == r) lans[x] = rans[x] = b;
else {
down(x, l, r);
int mid = l + r >> 1;
if(k <= mid) add(x << 1, l, mid, k, b);
else add(x << 1 | 1, mid + 1, r, k, b);
up(x);
}
}
inline void add(int x, int l, int r, int L, int R, ll k, ll b) {
// DEBUG
if(l > R || L > r) return;
if(L <= l && r <= R) {
tag3[x] = 1;
lans[x] = rans[x] = tag1[x] = tag2[x] = 0;
_add(x, l, r, k, b);
return;
}
down(x, l, r);
int mid = l + r >> 1;
add(x << 1, l, mid, L, R, k, b);
add(x << 1 | 1, mid + 1, r, L, R, k, b);
up(x);
}
inline void mogai(int x, int l, int r, int L, int R, ll b) {
// DEBUG
if(l > R || L > r) return;
if(L <= l && r <= R) {
_add(x, l, r, 0, b);
return;
}
down(x, l, r);
int mid = l + r >> 1;
mogai(x << 1, l, mid, L, R, b);
mogai(x << 1 | 1, mid + 1, r, L, R, b);
up(x);
}
inline void solve(int x, int l, int r, int L, int R, ll hmid, ll c1, ll c2) {
// DEBUG
if(l > R || L > r) return;
if(l == r) {
lans[x] = rans[x] = min(lans[x] + c2, hmid * l + c1);
return;
}
int mid = l + r >> 1;
down(x, l, r);
if(L > mid) solve(x << 1 | 1, mid + 1, r, L, R, hmid, c1, c2);
else if(R <= mid) solve(x << 1, l, mid, L, R, hmid, c1, c2);
else {
ll newl1 = hmid * mid + c1, newl2 = rans[x << 1] + c2;
ll newr1 = hmid * (mid + 1) + c1, newr2 = lans[x << 1 | 1] + c2;
if(newl1 <= newl2) add(x << 1, l, mid, L, mid, hmid, c1)/*, fprintf(stderr, "[%d, %d] choose way 1\n", l, mid)*/;
else solve(x << 1, l, mid, L, mid, hmid, c1, c2);
if(newr2 <= newr1) mogai(x << 1 | 1, mid + 1, r, mid + 1, R, c2)/*, fprintf(stderr, "[%d, %d] choose way 2\n", mid + 1, r)*/;
else solve(x << 1 | 1, mid + 1, r, mid + 1, R, hmid, c1, c2);
}
up(x);
}
// dp[l][i](i < mid) = dp[l][i]
// dp[l][i](i = mid) = dp[l][mid - 1] + h[mid]
// dp[l][i](i > mid) = min(h[mid] * i + dp[l][mid] - mid * h[mid], dp[mid + 1][i] + h[mid] * (mid - l + 1));
inline int build(int l, int r) {
// DEBUG
if(l == r) return l;
if(l > r) return 0;
int rt = rmq(l, r);
ls[rt] = build(l, rt - 1);
rs[rt] = build(rt + 1, r);
return rt;
}
inline void dfs(int x, int l, int r) {
// DEBUG
if(l > r) return;
dfs(ls[x], l, x - 1);
dfs(rs[x], x + 1, r);
// fprintf(stderr, "start [%d, %d]\n", l, r);
ll newhx = h[x];
if(ls[x]) newhx += get(1, 1, n, x - 1);
// fprintf(stderr, "dp[l][mid] = dp[%d][%d] = %lld\n", l, x, newhx);
add(1, 1, n, x, newhx);
if(rs[x]) {
for(int i = qhead[x + 1]; i; i = ques[i].nxt) {
// fprintf(stderr, "for ques [%lld, %lld], the ans without c is %lld\n", ques[i].l, ques[i].r, get(1, 1, n, ques[i].r));
ans[ques[i].id] = min(ans[ques[i].id], get(1, 1, n, ques[i].r) + ques[i].c);
}
solve(1, 1, n, x + 1, r, h[x], newhx - x * h[x], h[x] * (x - l + 1));
}
// fprintf(stderr, "end [%d, %d]\n", l, r);
}
inline void work() {
// DEBUG
memset(tag1, 0, sizeof tag1);
memset(tag2, 0, sizeof tag2);
memset(tag3, 0, sizeof tag3);
memset(lans, 0, sizeof lans);
memset(rans, 0, sizeof rans);
build_st();
int rt = build(1, n);
dfs(rt, 1, n);
for(int i = qhead[1]; i; i = ques[i].nxt) {
ans[ques[i].id] = min(ans[ques[i].id], get(1, 1, n, ques[i].r) + ques[i].c);
}
}
int main() {
// DEBUG
// freopen("hehezhou.in", "r", stdin);
// freopen("hehezhou.out", "w", stdout);
_max = _max1;
scanf("%d%d", &n, &q);
for(int i = 1; i <= n; i++) scanf("%lld", h + i);
build_st();
for(int l, r, i = 1; i <= q; i++) {
scanf("%d%d", &l, &r);
l++;
r++;
int x = rmq(l, r);
// fprintf(stderr, "%d\n", x);
ans[i] = h[x] * (r - l + 1);
if(x < r) addquery((x - l + 1) * h[x], x + 1, r, i, cur1);
if(x > l) addquery((r - x + 1) * h[x], n - x + 2, n - l + 1, i, cur2);
}
qhead = cur1;
work();
// for(int i = 1; i <= q; i++) printf("%lld\n", ans[i]);
qhead = cur2;
reverse(h + 1, h + 1 + n);
_max = _max2;
work();
for(int i = 1; i <= q; i++) printf("%lld\n", ans[i]);
return 0;
}