poj 3368 Frequent values 夜

RMQ+二分

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<math.h>

using namespace std;
int f[100005][21];
bool had[100005][21];
int a[100005];
long b[100005];
int n,q,m;
int dp(int i,int j)
{
    if(had[i][j]==true)
    {
        return f[i][j];
    }
    if(j==0)
    {
        had[i][j]=true;
        return f[i][j];
    }
    else
    {
        f[i][j]=max(dp(i,j-1),dp(i+(1<<(j-1)),j-1));
        had[i][j]=true;
        return f[i][j];
    }
}
inline int find(int k)
{
    int l=1,r=m,mid;
    while(l<r)
    {
        //cout<<l<<" "<<r<<endl;
        mid=(l+r)>>1;
        if(b[mid]==k)
        return mid;
        if(b[mid]<k)
        l=mid+1;
        else
        r=mid;
    }
    return l;
}
int main()
{
    //freopen("data.txt","r",stdin);
    //freopen("A-large-practice.out","w",stdout);
    while(scanf("%d",&n)!=EOF,n)
    {
        scanf("%d",&q);
        memset(b,0,sizeof(b));
        int l=1;
        for(int i=1;i<=n;++i)
        {
            scanf("%d",&a[i]);
            if(i==1||a[i]==a[i-1])
            {
                ++b[l];
            }
            else
            {
                ++l;
                b[l]=1;
            }

        }
        m=l;
        for(int i=1;i<=m;++i)
        {
            f[i][0]=b[i];
        }
        for(int i=1;i<=m;++i)
        {
            b[i]=b[i]+b[i-1];
        }
        for(int j=1;j<=(int)(log(1.0*m)/log(2.0));++j)
        {
            for(int i=1;i<=m+1-(1<<j);++i)
            {
                f[i][j]=max(dp(i,j-1),dp(i+(1<<(j-1)),j-1));
            }
        }
        int st,en,x,i,in,jn,j,ans,temp;
        while(q--)
        {
            scanf("%d%d",&st,&en);
            temp=0;
            int l=0;
            l=find(st);//cout<<"l=="<<l<<endl;
            in=b[l];
            i=l+1;
            l=find(en);//cout<<"l=="<<l<<endl ;
            j=l-1;
            jn=b[l-1];
            ans=0;

            //cout<<i<<" "<<in<<" "<<j<<" "<<jn<<endl;
            if(i-j==2)
            {
                ans=en-st+1;
            }
            else
            {
                ans=max(in-st+1,en-jn);
                if(i<=j)
                  {
                       x=0;
                       while((int)(pow(2.0,x)+0.5)<=j-i+1)
                       {
                        ++x;
                       }
                       --x;
                       ans=max(ans,max(f[i][x],f[j+1-(int)(pow(2.0,x)+0.5)][x]));
                  }
            }

            printf("%d\n",ans);
        }
    }

return 0;
}