UVA 11235 求区间连续数的众数 RMQ

题目链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2176

题意：

给定n长的序列， query次询问

下面n个数表示询问

对于每次询问的区间，回答该区间连续相同的数 这样的段最长有多长

思路：

RMQ裸题

特判下左右端点然后中间部分RMQ即可

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
using namespace std;
const int MAXN = 100100;
int n,query;
int A[MAXN];
int FMin[MAXN][20],FMax[MAXN][20];

void Init(){
	int i,j;
	for(i=1;i<=n;i++)
		FMin[i][0]=FMax[i][0]=A[i];
	for(i=1;(1<<i)<=n;i++){   //按区间长度递增顺序递推 
		for(j=1;j+(1<<i)-1<=n;j++){   //区间起点 
			FMin[j][i]=min(FMin[j][i-1],FMin[j+(1<<(i-1))][i-1]);
			FMax[j][i]=max(FMax[j][i-1],FMax[j+(1<<(i-1))][i-1]);
		}
	} 
}

int Query(int l,int r){
	int k=(int)(log(double(r-l+1))/log((double)2));
	return max(FMax[l][k],FMax[r-(1<<k)+1][k]);
}
int num[MAXN], l[MAXN], r[MAXN];

int main(){
	int i,j,a,b;
	while(scanf("%d",&n), n){
		scanf("%d",&query);
		int cnt = 1;
		int L = 1, R = 1;
		for(i=1;i<=n;i++)
		{
			scanf("%d",&num[i]);
			if(num[i] == num[i-1] && i!=1)
			{
				R++; cnt++;
			}
			if((i!=1 && num[i]!=num[i-1]) || i==n)
			{
				for(j = L; j <= R; j++)
				{
					A[j] = cnt;
					l[j] = L;
					r[j] = R;
				}
				cnt = 1;
				L = R = i;
			}
		}
		for(j = L; j <= n; j++)A[j] = cnt, l[j] = L, r[j] = n;
		Init();
		while(query--)
		{
			scanf("%d %d",&a,&b); if(a>b)swap(a,b);
			L = r[a]; if(L>=b){printf("%d\n", b-a+1);continue;}
			R = l[b]; if(R<=a){printf("%d\n", b-a+1);continue;}
			int ans = max(L-a+1, b-R+1);
			if(L == R-1){printf("%d\n", ans);continue;}
			L++, R--;
			printf("%d\n", max( ans, Query(L,R)));
		}
	}
	return 0;
}
/*
8 4
-1 -1 1 1 1 1 3 10
2 3
1 1
8 8
1 8

1 1
1
1 1

2 3
1 2
1 1
1 2
2 2

0
*/

UVA 11235 求区间连续数的众数 RMQ

原文：http://blog.csdn.net/acmmmm/article/details/19862701