题目链接：POJ - 2796
这是一个典型问题：需要你在短时间内求出所有的点左边/右边第一个比它大/小的位置。
应用：
方法一：利用已经得到的信息转移
以找到某个点左边/右边第一个比它小的位置为例（这里不包括那个比它小的点）：
- 当 \(a(i) < a(l_i - 1)\) 时，\(l_i = l_{l_i - 1}\)，直到满足 \(a(i) < a(l_i - 1)\)。
- 当 \(a(i) > a(r_i + 1)\) 时，\(r_i = r_{r_i + 1}\)，直到满足 \(a(i) > a(r_i + 1)\)。
初始化\(a_0 = a_{n+1} = -\infty\)，保证不会越界。
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
| #include <cstdio>
#include <algorithm>
#include <climits>
using namespace std;
typedef long long LL;
const int MAX_N = 1000000 + 5;
int n, a[MAX_N], lNext[MAX_N], rNext[MAX_N];
LL pre[MAX_N];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", a + i), pre[i] = pre[i - 1] + a[i];
a[0] = a[n + 1] = -INT_MAX;
for (int i = 1; i <= n; ++i) lNext[i] = rNext[i] = i;
for (int i = 1; i <= n; ++i) {
while (a[i] <= a[lNext[i] - 1]) lNext[i] = lNext[lNext[i] - 1];
}
for (int i = n; i >= 1; --i) {
while (a[i] <= a[rNext[i] + 1]) rNext[i] = rNext[rNext[i] + 1];
}
LL ans = -INT_MAX;
int ansL = -1, ansR = -1;
for (int i = 1; i <= n; ++i) {
if (ans < a[i] * (pre[rNext[i]] - pre[lNext[i] - 1])) {
ans = a[i] * (pre[rNext[i]] - pre[lNext[i] - 1]);
ansL = lNext[i]; ansR = rNext[i];
}
}
printf("%lld\n%d %d\n", ans, ansL, ansR);
return 0;
}
|
方法二：单调栈
维护一个单调栈，单调栈的顶部是左边/右边第一个比当前点小的点，如果需要不包含这个点，则左边+1右边-1即可。
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
| #include <cstdio>
#include <stack>
#include <algorithm>
#include <climits>
using namespace std;
typedef long long LL;
const int MAX_N = 1000000 + 5;
int n, a[MAX_N], lNext[MAX_N], rNext[MAX_N];
LL pre[MAX_N];
stack <int> s;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", a + i), pre[i] = pre[i - 1] + a[i];
while (!s.empty()) s.pop();
for (int i = 1; i <= n; ++i) {
while (!s.empty() && a[s.top()] >= a[i]) s.pop();
lNext[i] = (s.empty() ? 1 : s.top() + 1);
s.push(i);
}
while (!s.empty()) s.pop();
for (int i = n; i >= 1; --i) {
while (!s.empty() && a[s.top()] >= a[i]) s.pop();
rNext[i] = (s.empty() ? n : s.top() - 1);
s.push(i);
}
LL ans = -INT_MAX;
int ansL = -1, ansR = -1;
for (int i = 1; i <= n; ++i) {
if (ans < a[i] * (pre[rNext[i]] - pre[lNext[i] - 1])) {
ans = a[i] * (pre[rNext[i]] - pre[lNext[i] - 1]);
ansL = lNext[i]; ansR = rNext[i];
}
}
printf("%lld\n%d %d\n", ans, ansL, ansR);
return 0;
}
|