自己出了一道题，感觉挺有意思的。
题目
一个长度为\(n\)的序列，将每个子序列的权值定义为\(\min(a-l,a_{l+1},...,a-r)\times
\max(a-l,a_{l+1},...,a-r)\)。 对于所有长度不小于\(k\)的连续子序列，要你求出一段权值严格次大的子序列。如果不存在这样的子序列，输出最大的权值。
题解
因为总是会有一个数作为最小值，所以直接枚举每个数作为区间最小值。
当某个数\(a-i\)做最小值时，用单调栈分别算出\(a-i\)最多向左和向右延伸的最长长度。记为\(L-i\)和\(R-i\)。
如果\(R-i-L-i+1\geq
k\)，那么就可以把\(a-i\times
max(a-l,a_{l+1},...,a-r)\)记录下来，因为它有可能成为答案。把\(max(a-l,a_{l+1},...,a-r)\)记为\(MAX\)。
但是要求次大值。当\(a-i\)作为最小值时，需要找到一个区间\([l-0,r-0]\)使\(max(a[l-0] \sim a[r-0])\)与\(MAX\)不同。并且\(r-0-l-0\)尽量大，那么就找到了这个次大值。具体方法是开桶记录每个元素的位置，查出与\(a-i\)相邻的两个\(MAX\)的位置，与\([L-i,R-i]\)取一个交集就是\([l-0,r-0]\)了。一样的方法把次大的权值记录下来。
处理完之后就能得到次小或者最大的权值了，注意细节就可以。
时间复杂度\(\mathjaxcal{O}(nlogn)\)，主要瓶颈是找区间最大值上。
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
int n, k, a[N], l[N], r[N], q[N], f[N][21], bit[N];
vector<int> v[N];
ll max1, max2;
int read() {
char ch = getchar();
int w = 0;
while(ch < '0' || ch > '9') ch = getchar();
while(ch >= '0' && ch <= '9') {
w = w * 10 + ch - 48;
ch = getchar();
}
return w;
}
void pre() {
bit[0] = 1;
for(int i = 1; i <= 20; i++) bit[i] = bit[i - 1] * 2;
int logn2 = (int)(log(n) / log(2));
for(int i = 1; i <= n; i++) f[i][0] = a[i];
for(int j = 1; j <= logn2; j++)
for(int i = 1; i <= n - bit[j] + 1; i++) {
f[i][j] = max(f[i][j - 1], f[i + bit[j-1]][j-1]);
}
int head = 1, tail = 0;
for(int i = 1; i <= n; i++) {
while(head <= tail && a[q[tail]] >= a[i]) tail--;
if(tail < head) l[i] = 1;
else l[i] = q[tail] + 1;
q[++tail] = i;
}
tail = 0;
for(int i = n; i >= 1; i--) {
while(head <= tail && a[q[tail]] >= a[i]) tail--;
if(tail < head) r[i] = n;
else r[i] = q[tail] - 1;
q[++tail] = i;
}
}
int query(int l, int r) {
int logn2=(int) (log(r - l + 1) / log(2));
return max(f[l][logn2], f[r - bit[logn2] + 1][logn2]);
}
void update(ll x) {
if(x > max1) {
max2 = max1;
max1 = x;
} else if(x < max1 && x > max2) {
max2 = x;
}
}
int main() {
n = read(); k = read();
for(int i = 1; i <= n; i++) {
a[i] = read();
v[a[i]].push-back(i);
}
pre();
for(int i = 1; i <= n; i++) {
if(r[i] - l[i] + 1 < k) continue;
int MAX = query(l[i], r[i]);
update(MAX * 1ll * a[i]);
if(a[i] == MAX) continue;
int y = lower-bound(v[MAX].begin(), v[MAX].end(), i) - v[MAX].begin(), l0, r0;
if(y == v[MAX].size()) r0 = n;
else r0 = v[MAX][y] - 1;
--y;
if(v[MAX][y] == i) --y;
if(y < 0) l0 = 1;
else l0 = v[MAX][y] + 1;
l0 = max(l0, l[i]); r0 = min(r0, r[i]);
if(r0 - l0 + 1 < k || r0 < i || l0 > i) continue;
update(query(l0, r0) * 1ll * a[i]);
}
if(!max2) printf("%lld\n", max1);
else printf("%lld\n", max2);
return 0;
}
|