//離散化+st ?
#include <iostream>
#include <math.h>
using namespace std;
int a[100005];
int index[100005];
int f[100005];
int start[100005];
int mf[100005][100];
int n;
void rmq_init()
{
int i,j,k=floor(log(double(n))/log(2.0));
for(i=1; i<=n; i++) mf[i][0]=f[i];
for(j=1; j<=k; j++)
for(i=1; i+(1<<(j-1))<=n; i++)
mf[i][j]=max(mf[i][j-1],mf[i+(1<<(j-1))][j-1]);
}
int rmq(int l,int r)
{
int il,ir, m,k;
il=index[a[l]],ir=index[a[r]];
if(il==ir)
return r-l+1;
else
if(il+1==ir)
return max(start[ir]-l, r-start[ir]+1);
else
{
m=max( start[il+1]-l, r-start[ir]+1);
il++,ir--;
k=floor(log(double(ir-il+1))/log(2.0));
m=max( m, max(mf[il][k], mf[ir-(1<<k)+1][k]));
return m;
}
}
int main()
{
int i,N,Q,l,r;
while(scanf("%d", &N)!=EOF && N)
{
scanf("%d", &Q);
memset(f, 0, sizeof(f));
for(a[0]=0,i=1, n=0; i<=N; i++)
{
scanf("%d", a+i);
if(a[i]!=a[i-1])
index[ a[i] ]=++n, start[n]=i;
f[n]++;
}
rmq_init();
for(i=0; i<Q; i++)
{
scanf("%d%d", &l, &r);
printf("%d\n", rmq(l,r));
}
}
return 0;
}
posted on 2010-03-27 14:50
wyiu 閱讀(427)
評(píng)論(1) 編輯 收藏 引用 所屬分類(lèi):
POJ