(所有數(shù)組下標從1計)計算出原數(shù)列中每個數(shù)出現(xiàn)次數(shù)的數(shù)列，并用RMQ預處理
如 a[]={ -1 -1 1 1 1 1 3 10 10 10} 得到 sum[]={ 2 4 1 3 }
用index數(shù)組記錄a[i]在sum中的下標。index[]={1,1,2,2,2,2,3,4,4,4};
first數(shù)組記錄每組數(shù)據(jù)中第一個出現(xiàn)的在a中的下標
first[]={1,3,7,8};
對于每個詢問的區(qū)間[from,to],首先計算出from to在sum中對應的位置f，t
1、如果f==t，則[from,to]區(qū)間中數(shù)據(jù)是一樣的
2、如果f+1=t，則[from,to]區(qū)間只有兩種數(shù)據(jù)。
3、如果f+1<t，則[from,to]區(qū)間有大于兩種數(shù)據(jù)
#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));
}
}
}