题目类型 RMQ
题目意思
给出最多包含100000个数的非递减数列 有最多100000次询问 每次询问 第 L 个数到第 R 个数之间最长的每个数都相同的连续子序列是多长
解题方法
可以使用ST算法
首先预处理 把原数列连续相同部分压缩成一个整数 例如 1 1 1 2 2 3 3 3 3 压缩成 3 2 4 并记录压缩后每个数对应的原子序列的开头位置
然后预处理一个数组 dp[i][j] 表示从第 i 个位置开始 (1<<j) 个数这个范围内的最大值
那么对于一个询问 L->R 首先求出 L这个位置往后还有多少是相同的 再求出从R这个位置往前有多少个相同的 记录它们的最大值与中间那些连续相同段对应的数进行比较 具体看代码
参考代码 - 有疑问的地方在下方留言 看到会尽快回复的
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 10;
const int INF = 1<<29;
const double e = 2.71828;
int a[maxn], b[maxn], num[maxn], sta[maxn];
int dp[maxn][20];
int main() {
//freopen("in", "r", stdin);
int n, q;
while(scanf("%d%d", &n, &q) == 2) {
memset(dp, 0, sizeof(dp));
for( int i=0; i<n; i++ ) {
scanf("%d", &a[i]);
}
int pre = a[0], cut = 1;
int tn = 0; //tn表示有多少不同的相同连续子段
sta[0] = 0; //这个数组保存每个相同连续子段的开始位置
for( int i=1; i<n; i++ ) {
if(a[i] == pre) cut++;
else {
b[tn] = a[i-1]; //ｂ数组保存每个相同连续子段包含的数字个数
num[tn++] = cut;
sta[tn] = i;
cut = 1;
pre = a[i];
}
}
b[tn] = a[n-1]; num[tn++] = cut;
for( int i=0; i<tn; i++ ) dp[i][0] = num[i]; //预处理dp数组
for( int j=1; (1<<j)<tn; j++ ) {
for( int i=0; i<tn && i+(1<<j)-1<tn; i++ ) {
dp[i][j] = max(dp[i][j-1], dp[i+(1<<j)-1-(1<<(j-1))+1][j-1]);
}
}
for( int i=0; i<q; i++ ) {
int l, r;
scanf("%d%d", &l, &r);
l--, r--;
int L = lower_bound(b, b + tn, a[l]) - b;
int R = lower_bound(b, b + tn, a[r]) - b;
int ans = 0;
if(L == R) ans = max(ans, r-l+1);
else {
ans = max(ans, sta[L+1] - l); // 与L相同的在L到R之间的数的个数
ans = max(ans, r - sta[R] + 1); //与R相同的在L到Ｒ之间的数的个数
if(L+1 != R) {
double tk = log(1.0*R-1-(L+1)+1)/log(2.0);
int tmp = tk;
ans = max(ans, max(dp[L+1][tmp], dp[R-1-(1<<tmp)+1][tmp]));
}
}
printf("%d\n", ans);
}
}
return 0;
}