(所有数组下标从1计)计算出原数列中每个数出现次数的数列，并用RMQ预处理
如 a[]={ -1 -1 1 1 1 1 3 10 10 10} 得到 sum[]={ 2 4 1 3 }
用index数组记录a[i]在sum中的下标。index[]={1,1,2,2,2,2,3,4,4,4};
first数组记录每组数据中第一个出现的在a中的下标
first[]={1,3,7,8};
对于每个询问的区间[from,to],首先计算出from to在sum中对应的位置f，t
1、如果f==t，则[from,to]区间中数据是一样的
2、如果f+1=t，则[from,to]区间只有两种数据。
3、如果f+1<t，则[from,to]区间有大于两种数据
#include<iostream>
#include<vector>
#include<string>
#include<cmath>
using namespace std;
const int maxsize=100001;
int sum[maxsize],st[maxsize][20],a[maxsize],index[maxsize],first[maxsize];
void rmq_init(int len)
{
for(int i=1;i<=len;i++)
st[i][0]=sum[i];
int m=floor(log((double)len)/log(2.0));
for(int i=1;i<=m;i++)
for(int j=len;j>0;j--)
{
st[j][i]=st[j][i-1];
if(i+(1<<(i-1))<=len) st[j][i]=max(st[j][i],st[j+(1<<(i-1))][i-1]);
}
}
int query(int l,int r)
{
int m=floor(log((double)(r-l+1))/log(2.0));
return max(st[l][m],st[r-(1<<m)+1][m]);
}
int solve(const int & from,const int & to)
{
int f=index[from],t=index[to];
if(f==t) return to-from+1;
else if(f+1==t) return max(first[t]-from,to-first[t]+1);
else
{
int res;
res=max(first[f+1]-from,to-first[t]+1);
res=max(res,query(f+1,t-1));
return res;
}
}
int main()
{
int from,to;
int n,q;
int len;
while(scanf("%d",&n)!=EOF)
{
if(n==0) break;
scanf("%d",&q);
a[0]=INT_MAX;
len=0;
memset(sum,0,sizeof(sum));
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]==a[i-1])
{
index[i]=len;
sum[len]++;
}
else
{
index[i]=++len;
sum[len]=1;
first[len]=i;
}
}
rmq_init(len);
while(q--)
{
scanf("%d%d",&from,&to);
printf("%d\n",solve(from,to));
}
}
}