题目链接：
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2176RMQ问题，《算法竞赛入门经典——训练指南》上的例题。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 100005;
int n, q;
int a[maxn];
int len;
int val[maxn], cnt[maxn];
int num[maxn], lef[maxn], rig[maxn];
int d[maxn][20];
void RLE_proc() 
{
len = 0;
for(int i = 0; i < n; ) {
int j = i + 1;
while(a[j] == a[i] && j < n) j++;
val[len] = a[i];
cnt[len] = j - i;
for(int k = i; k < j; k++) {
num[k] = len;
lef[k] = i;
rig[k] = j - 1;
}
len++;
i = j;
}
}
void RMQ_init() {
for(int i = 0; i < len; i++) d[i][0] = cnt[i];
for(int j = 1; (1<<j) <= len; j++)
for(int i = 0; i + (1<<j) - 1 < len; i++)
d[i][j] = max(d[i][j-1], d[i + (1<<(j-1))][j-1]);
}
int RMQ_query(int a, int b) {
int k = int(log(b-a+1) / log(2.0));
return max(d[a][k], d[b- (1<<k) + 1][k]);
}
int main()
{
while(scanf("%d", &n) != EOF && n) {
scanf("%d", &q);
for(int i = 0; i < n; i++) scanf("%d", &a[i]);
RLE_proc();
RMQ_init();
int a, b;
for(int i = 0; i < q; i++) {
scanf("%d%d", &a, &b);
a--;
b--;
if(num[a] == num[b]){
printf("%d\n", b-a+1);
} else {
int ans = max(rig[a]-a+1, b-lef[b]+1);
if(num[a]+1 <= num[b]-1) {
ans = max(ans, RMQ_query(num[a]+1, num[b]-1));
}
printf("%d\n", ans);
}
}
}
return 0;
}
posted on 2013-06-15 17:34
wuxu 阅读(263)
评论(0) 编辑 收藏 引用 所属分类:
数据结构