题目描述
https://www.luogu.com.cn/problem/P3512
Solution
这里提供一个 $O(n)$ 做法
其实直接枚举右端点，然后左端点是单调的，双指针加单调队列就能做
但是我们考虑左端点移动时一定改变最大或者最小值
而改变这些值的位置就是单调队列中所维护的后缀最小/最大值
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 <iostream>
#include <cstdio>
#include <cctype>
#define maxn 3000010
#define gc getchar
using namespace std;
int read() {
int x = 0; char c = gc();
while (!isdigit(c)) c = gc();
while (isdigit(c)) x = x * 10 + c - '0', c = gc();
return x;
}
int n, m, a[maxn];
int Q1[maxn], h1, t1, Q2[maxn], h2, t2;
int ans;
int main() {
m = read(); n = read(); h1 = h2 = 1;
for (int i = 1; i <= n; ++i) a[i] = read();
for (int i = 1; i <= n; ++i) {
while (h1 <= t1 && a[i] <= a[Q1[t1]]) t1--;
Q1[++t1] = i;
while (h2 <= t2 && a[i] >= a[Q2[t2]]) t2--;
Q2[++t2] = i;
while (h1 <= t1 && h2 <= t2 && a[Q2[h2]] - a[Q1[h1]] > m) {
if (Q1[h1] < Q2[h2]) ++h1;
else ++h2;
}
ans = max(ans, i - max(Q2[h2 - 1], Q1[h1 - 1]));
} cout << ans << endl;
return 0;
}
|