题目链接：
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2176
RMQ，就是范围最小值的缩写，这个算法是Tarjan 的 Sparse-Table 算法，复杂度为O（n*log(n)）.
就是用数组d[i][j]表示范围[i,i+2^j-1]中的最小值。
然后有递推式
d[i][j] = min(d[i][j-1],d[i+2^(j-1)][j-1]).
有边界条件d[i][0] = A[i].
然后就能求出所有的d[i][j].查询时只需找出2^（k+1） <= R-L+1的最大的k值，取等号时，k要+1.
答案为min(d[L][k],d[R-(1<<k)+1][k]).这两个区间有重叠，木有关系的，不是吗？
本题用Sparse-Table算法，改成求最大值即可。具体解法采用游程编码。
如输入的数组为-1,-1,1,1,1,1,3,10,10,10.则能得到(-1,2),(1,4),(3,1),(10,3),（a,b）表示值为a的数有b个。
然后将数组分为4块，编号分别为1,2,3,4.用辅助数组num[i],left[i],right[i]记录位置i所在的块的编号，以及块的左端点和右端点位置。
数组 -1,-1,1,1,1,1,3,10,10,10.
num 1, 1,2,2,2,2,3,4, 4, 4.
left 1 , 1,3,3,3,3,7,8, 8, 8.
right 2, 2,6, 6,6,6,7,10,10,10
然后答案为max(right(L)-L+1 , R - left[R]+1, max (num[L]+ 1, num[R] - 1));
特判当L和R在同一段时答案是R-L+1.
当num[L]+1 > num[R]-1时，最大值为负无穷。
贴代码：
#include<cstdio>
#include<algorithm>
using namespace std;
const int N =;
int c;
//元素从1编到n
int d[N][],n,cnt[N],num[N],left[N],right[N];
void RMQ_init()
{
for(int i=; i<=c; ++i) d[i][] = cnt[i];
for(int j=; (<<j) <= c; ++j)
for(int i=; i+j-<=c; ++i)
d[i][j] = max(d[i][j-],d[i+(<<(j-))][j-]);
}
int RMQ(int L,int R)
{
if(L>R) return ;
int k=;
while((<<(k+)) <= R-L+) ++k;
return max(d[L][k],d[R-(<<k)+][k]);
}
int main()
{
// freopen("in.txt","r",stdin);
int n,Q,a;
while(scanf("%d",&n),n)
{
for(int i=; i<=n; ++i) cnt[i]=;
scanf("%d%d",&Q,&a);
int p = a;
c=,cnt[c] = ,num[] = c;
for(int i=; i<=n; ++i)
{
scanf("%d",&a);
if(a != p)
{
p = a;
++c;
}
++cnt[c];
num[i] = c;
}
int s =;
for(int i=; i<=c; ++i)
{
for(int j=; j<=cnt[i]; ++j)
left[s+j] = s+,right[s+j] = s+cnt[i];
s += cnt[i];
}
RMQ_init();
while(Q--)
{
int l,r;
scanf("%d%d",&l,&r);
if(num[l] == num[r])
{
printf("%d\n",r-l+);
continue;
}
int ans=right[l]-l+;
if(r-left[r]+ > ans) ans = r-left[r]+;
int d = RMQ(num[l]+,num[r]-);
if(d > ans) ans =d;
printf("%d\n",ans);
}
}
return ;
}