HDU 1806

http://acm.hdu.edu.cn/showproblem.php?pid=1806

非常玄妙的rmq问题，这个st算法有点神

#include <iostream>
#include <cmath>
using namespace std ;
int dp[100005][20] ;
int a[100005],b[100005] ;
void makermq(int n,int *tt)
{
    for(int i=0 ;i<n ;i++)
        dp[i][0]=tt[i] ;
    for(int j=1 ;(1<<j)<=n ;j++)
        for(int i=0 ;i+(1<<j)-1<n ;i++)
            dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]) ;
} 
int rmq(int l,int r)
{
    int k=(int)(log((r-l+1)*1.0)/log(2)) ;
    return max(dp[l][k],dp[r-(1<<k)+1][k]) ;
}
int bs(int l,int r)
{
    int temp=a[r] ;
    while(l<r)
    {
        int mid=(l+r)>>1 ;
        if(a[mid]>temp)
            r=mid-1 ;
        else if(a[mid]<temp)
            l=mid+1 ;
        else
            r=mid ;
    }
    return r ;
}
int main()
{
    int n,q ;
    while(~scanf("%d",&n),n)
    {
        scanf("%d",&q) ;
        for(int i=0 ;i<n ;i++)
            scanf("%d",&a[i]) ;
        int cnt ;
        for(int i=n-1 ;i>=0 ;i--)
        {
            if(i==n-1)
                cnt=1 ;
            else
            {
                if(a[i]==a[i+1])
                    cnt++ ;
                else
                    cnt=1 ;
            }
            b[i]=cnt ;
        }
        makermq(n,b) ;
        while(q--)
        {
            int l,r ;
            scanf("%d%d",&l,&r) ;
            l-- ;r-- ;
            int temp=bs(l,r) ;
            int ans=r-temp+1 ;
            r=temp-1 ;
            if(l>r)
                printf("%d
",ans) ;
            else 
                printf("%d
",max(ans,rmq(l,r))) ;
        }
    }
    return 0 ;
}