题目大意:
求所有极差不超过 \(k\) 的最长连续子序列。
解题思路:
先开一个 ST 表方便求解区间最大值和区间最小值。
然后基于倍增思想(详见 cal
函数)求极差不超过 \(k\) 的最长连续子序列。
示例程序:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n, k, mx[maxn][18], mi[maxn][18], a[maxn], res[maxn];
int cal(int p) {
int len = 1, x = a[p], y = a[p];
for (int i = 17; i >= 0; i--)
if (p + (1<<i) <= n && max(x, mx[p+1][i]) - min(y, mi[p+1][i]) <= k)
len += 1<<i,
x = max(x, mx[p+1][i]),
y = min(y, mi[p+1][i]),
p += 1<<i;
return len;
}
int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++)
scanf("%d", a+i), mx[i][0] = mi[i][0] = a[i];
for (int j = 1; j < 18; j++)
for (int i = 1; i+(1<<j)-1 <= n; i++)
mx[i][j] = max(mx[i][j-1], mx[i+(1<<j-1)][j-1]),
mi[i][j] = min(mi[i][j-1], mi[i+(1<<j-1)][j-1]);
int x = 0, cnt = 0;
for (int i = 1; i <= n; i++) {
res[i] = cal(i);
if (res[i] > x) x = res[i], cnt = 1;
else if (res[i] == x) cnt++;
}
printf("%d %d\n", x, cnt);
for (int i = 1; i <= n; i++)
if (res[i] == x)
printf("%d %d\n", i, i+x-1);
return 0;
}
标签:cnt,int,题解,ST,CF6E,maxn,res,Exposition,倍增
From: https://www.cnblogs.com/quanjun/p/17445666.html