#include <stdio.h>
#include <iostream>
#include <math.h>
#include <string.h>
using namespace std;
const int maxn=100005;
int a[maxn+10];
int in[2*maxn+10];
int f[maxn+10];
int dp[30][maxn+10];
int start[maxn+10];
int n, q, cnt;
void buildRmq()
{
    for (int i=1; i<=cnt; i++) dp[0][i]=f[i];
    for (int i=1; (1<<i)<=cnt; i++)
        for (int j=1; (j+(1<<(i-1)))<=cnt; j++)
            dp[i][j]=max(dp[i-1][j], dp[i-1][j+1<<(i-1)]);
}
int Query(const int &l, const int &r)
{
    int x=a[l], y=a[r];
    int c=in[x], b=in[y];
    if (c==b) return b-c+1;
    else if (c+1==b) return max(start[b]-l, r-start[b]+1);
    else
    {
        int m=max(start[c+1]-l, r-start[b]+1);
        c++, b--;
        int k=(int)floor(log(b-c+1.0)/log(2.0));
        return max(m, max(dp[k][c], dp[k][b-(1<<k)+1]));
    }
}
int main()
{
    freopen("in.txt", "r", stdin);
    while (scanf("%d", &n), n)
    {
        scanf("%d", &q);
        memset(f, 0, sizeof(f));
        a[0]=0;
        cnt=0;
        for (int i=1; i<=n; i++)
        {
            scanf("%d", &a[i]);
            a[i]+=maxn;

            if (a[i] !=a[i-1]) in[a[i]]=++cnt, start[cnt]=i;
            f[cnt]++;
        }
        buildRmq();
        for (int i=0; i<q; i++)
        {
            int x, y;
            scanf("%d %d", &x, &y);
            if (x>y) printf("%d\n", Query(y, x));
            else printf("%d\n", Query(x, y));
        }
    }
    return 0;
}

• Re:3368 RE N次 跪求大牛帮看看阿～～～～～～～～～～～～ (1606) langbing2011 2011-08-22 18:26:52