19牛客多校第四场C(枚举+前缀和+单调栈)
题意
给你两个长度为$n$的序列,第一个称为$a$,第二个称为$b$ .然后求$\displaystyle \max_{1 \le l \le r \le n} {min(a_{l \dots r}) \times sum(b_{l \dots r})}$
分析
首先不难想到通过前缀和以及ST表优化只有,此题有$O(n^2)$的做法,也就是枚举左右端点,然后O(1)查询的方法.(当然,这个题卡空间,如果用ST表还需要一些小技巧).
所以怎么样才能不用枚举呢?我们发现一个问题,就是枚举的过程中,对于相当多的$[l,r]$ ,区间中a的最小值其实是不变的.也就是说,如果我们考虑枚举a作为区间最小值,然后通过某种方法预处理出了b在此a作用范围内的和的最大值,那么就可以降低复杂度了.
具体来讲,我们发现,a如果是区间$[l,r]$ 的最小值,且无法继续向两边扩展的唯一情况是$a[l-1]$和$a[r+1]$ 都比它小(此处假设数组边界处存在无穷小的值).
根据单调栈,我们可以在$O(n)$的时间内预处理两个数组$l[]$,$r[]$ ,分别表示当前元素左侧第一个比它小的元素的下标.
然后我们对$b[]$求前缀和,然后维护一下区间最大值和最小值查询.然后遍历数组$a[]$ ,对于每个元素,都查询其作用范围下$b[]$的极值,然后统计乘积最大值.
AC代码
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
221
222
223
#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define maxn 3000000+100
int a[maxn];
int L[maxn], R[maxn];
int stk[maxn];
ll sum[maxn];
// int dpmax[maxn][23];
ll ss[maxn];
int n;
int pos = 0;
const int Inf = 0x3f3f3f3f;
struct t {
ll lazy;
int l, r;
ll sum, Max, Min;
} t[(maxn << 2) + 5];
bool EQ(const char *a, const char *b) {
if (strcmp(a, b) == 0)
return true;
else
return false;
}
void pushup(int rt) {
t[rt].sum = t[rt << 1].sum + t[rt << 1 | 1].sum;
t[rt].Max = max(t[rt << 1].Max, t[rt << 1 | 1].Max);
t[rt].Min = min(t[rt << 1].Min, t[rt << 1 | 1].Min);
}
void build(int rt, int l, int r) { //建立线段树及初始化操作
t[rt].lazy = 0;
t[rt].l = l;
t[rt].r = r;
if (t[rt].l == t[rt].r) {
t[rt].sum = sum[l];
t[rt].Max = sum[l];
t[rt].Min = sum[l];
return;
}
int mid = (l + r) >> 1;
build(rt << 1, l, mid); //建立左子树
build(rt << 1 | 1, mid + 1, r); //建立右子树
pushup(rt);
}
void update(int rt, int id, int val) { //线段树的点更改
if (t[rt].l == t[rt].r) { //叶子节点
t[rt].sum = val;
t[rt].Max = val;
t[rt].Min = val;
return;
}
int mid = (t[rt].l + t[rt].r) >> 1;
if (id <= mid)
update(rt << 1, id, val);
if (id >= mid + 1)
update(rt << 1 | 1, id, val);
pushup(rt);
}
void pushdown(int rt, int m) {//pushdown函数
if (t[rt].lazy) { //若有标记,则将标记向下移动一层
t[rt << 1].lazy += t[rt].lazy;
t[rt << 1 | 1].lazy += t[rt].lazy;
t[rt << 1].sum += (m - (m >> 1)) * t[rt].lazy;
t[rt << 1 | 1].sum += (m >> 1) * t[rt].lazy;
t[rt << 1].Min += t[rt].lazy;
t[rt << 1 | 1].Min += t[rt].lazy;
t[rt << 1].Max += t[rt].lazy;
t[rt << 1 | 1].Max += t[rt].lazy;
t[rt].lazy = 0;//取消本层标记
}
}
void update_lazy(int rt, int ql, int qr, int addval) { //区间加值
if (t[rt].l >= ql && t[rt].r <= qr) {
t[rt].lazy += addval;
t[rt].sum += addval * (t[rt].r - t[rt].l + 1);
t[rt].Max += addval;
t[rt].Min += addval;
return;
}
pushdown(rt, t[rt].r - t[rt].l + 1); //当前节点更新信息传递到下一层
int mid = (t[rt].l + t[rt].r) >> 1;
if (ql <= mid)
update_lazy(rt << 1, ql, qr, addval);
if (qr >= mid + 1)
update_lazy(rt << 1 | 1, ql, qr, addval);
pushup(rt);
}
ll GetSum(int rt, int ql, int qr) {
if (ql <= t[rt].l && qr >= t[rt].r)
return t[rt].sum;
pushdown(rt, t[rt].r - t[rt].l + 1);
int mid = (t[rt].l + t[rt].r) >> 1;
ll ans = 0;
if (ql <= mid)
ans += GetSum(rt << 1, ql, qr);
if (qr >= mid + 1)
ans += GetSum(rt << 1 | 1, ql, qr);
return ans;
}
ll GetMax(int rt, int ql, int qr) {
if (ql <= t[rt].l && qr >= t[rt].r) {
return t[rt].Max;
}
pushdown(rt, t[rt].r - t[rt].l + 1);
int mid = (t[rt].l + t[rt].r) >> 1;
ll ans = -Inf;
if (ql <= mid)
ans = max(ans, GetMax(rt << 1, ql, qr));
if (qr >= mid + 1)
ans = max(ans, GetMax(rt << 1 | 1, ql, qr));
return ans;
}
ll GetMin(int rt, int ql, int qr) {
if (ql <= t[rt].l && qr >= t[rt].r) {
return t[rt].Min;
}
pushdown(rt, t[rt].r - t[rt].l + 1);
int mid = (t[rt].l + t[rt].r) >> 1;
ll ans = Inf;
if (ql <= mid)
ans = min(ans, GetMin(rt << 1, ql, qr));
if (qr >= mid + 1)
ans = min(ans, GetMin(rt << 1 | 1, ql, qr));
return ans;
}
template<typename T>
inline void read(T &X) {
X = 0;
char ch = 0;
T op = 1;
for (; ch > '9' || ch < '0'; ch = getchar())
if (ch == '-') op = -1;
for (; ch >= '0' && ch <= '9'; ch = getchar())
X = (X << 3) + (X << 1) + ch - 48;
X *= op;
}
int main() {
// read(n);
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
//read(a[i]);
scanf("%d", &a[i]);
}
sum[0] = 0ll;
for (int i = 1; i <= n; ++i) {
int tmp;
// read(tmp);
scanf("%d", &tmp);
sum[i] = sum[i - 1] + tmp;
}
pos = 0;
for (int i = 1; i <= n; ++i) {
while (pos && a[stk[pos - 1]] >= a[i]) {
--pos;
}
if (!pos) {
L[i] = 0;
} else {
L[i] = stk[pos - 1];
}
stk[pos++] = i;
}
// for (int i = 1; i <= n; ++i) {
// printf("%d ", L[i]);
// }
// printf("\n");
pos = 0;
for (int i = n; i >= 1; --i) {
while (pos && a[stk[pos - 1]] >= a[i]) {
--pos;
}
if (!pos) {
R[i] = n + 1;
} else {
R[i] = stk[pos - 1];
}
stk[pos++] = i;
}
build(1, 1, n);
// rmq_init();
for (int i = 1; i <= n; ++i) {
if (a[i] < 0) {
ss[i] = GetMax(1, L[i], i - 1);
} else if (a[i] > 0) {
ss[i] = GetMax(1, i, R[i] - 1);
}
}
// for (int i = 1; i <= n; ++i) {
// printf("%d ", R[i]);
// }
// printf("\n");
// for (int i = 1; i <= n; ++i) {
// printf("%lld ", sum[i]);
// }
// printf("\n");
ll ans = a[1] * sum[1];
for (int i = 1; i <= n; ++i) {
if (a[i] < 0) {
ans = max(ans, a[i] * (GetMin(1, i, R[i] - 1) - ss[i]));
} else if (a[i] > 0) {
ans = max(ans, a[i] * (ss[i] - GetMin(1, L[i], i - 1)));
} else {
ans = max(ans, 0ll);
}
}
printf("%lld\n", ans);
return 0;
}
这个题有点不友好,ST表卡空间需要先处理最大值,然后记录下,然后再处理最小值.也就是dp数组反复利用,但是这样写又会超时.
后来我发现,即使是线段树,也需要加快读才能过.
这个题还有个解法是笛卡尔树,但是并没有找到合适的资料,只能作罢,不过时间复杂度是非常优秀的$O(n)$.
