Uva 11235 RMQ ST 알고리즘

RMQ 문제 정적 구간 의 가장 값 을 구 합 니 다.
http://blog.chinaunix.net/uid-20760412-id-1872571.html
http://blog.csdn.net/detective_xin/article/details/7211135
이 문 제 는 아이디어 도 좋 습 니 다. 처음에는 RMQ 를 사용 할 수 없 었 습 니 다. 여기 에는 여정 인 코딩 을 사용 하여 같은 연속 숫자 를 한 단락 으로 압축 하여 이 단락 의 데이터 개 수 를 기록 한 다음 에 RMQ 로 단락 의 가장 값 을 계산 합 니 다.
물론 전환 문제 도 있다.
value [], Count [] 는 각 단락 의 값 과 개 수 를 기록 하 는 데 사용 된다.
L [], R [], num [] 은 각 단락 의 가장 왼쪽 끝 과 가장 오른쪽 끝 을 기록 하고 특정한 점 이 어느 단락 에 속 하 는 지 기록 하 는 데 사용 된다.
쌍 당 l, r, l 과 r 가 한 단락 에 있 으 면 r - l + 1 이 고 그렇지 않 으 면 R [num [l] - l + 1, r - L [num [r] + 1, RMQ (num [l] + 1, num [r] - 1) 의 최대 치 입 니 다.
코드:

#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<queue>
#include<cmath>
#include<algorithm>
#include<cstring>
#define maxn 1000005
#define maxm 1000005
#define INF 0xfffffff
#define mem(a,b) memset(a,b,sizeof(a))
#define FOR(i,s,t) for(int i=s;i<=t;i++)
#define ull unsigned long long
#define ll long long
using namespace std;
int value[maxn],Count[maxn];
int L[maxn],R[maxn],num[maxm];//          ，      ，        
int dp[maxn][33];
void init()
{
    memset(Count,0,sizeof(Count));
    memset(dp,0,sizeof(dp));
}
int n,q;
void init_RMQ(int k)
{
    for(int i=1;i<=k;i++)
    dp[i][0]=Count[i];

    for(int j=1;(1<<j)<=k;j++)
    {
        for(int i=1;i+(1<<j)-1<=k;i++)
        {
            dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
        }
    }
}
int RMQ(int l,int r)
{
    if(r<l) return 0;
    int k=0;
    while((1<<k+1)<=r-l+1) k++;//     [l,r]    k  2^k<=r-l+1
    return max(dp[l][k],dp[r-(1<<k)+1][k]);
}
int main()
{
    while(scanf("%d",&n)==1)
    {
        if(!n) break;
        init();
        scanf("%d",&q);
        int k=1,a;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a);
            if(i==1)
            {
                Count[k]++;
                value[k]=a;
                num[i]=k;
                L[k]=i;
                continue;
            }
            if(value[k]!=a)
            {
                R[k]=i-1;
                k++;
                L[k]=i;
                value[k]=a;
                Count[k]++;
                num[i]=k;
            }
            else
            {
                Count[k]++;
                num[i]=k;
            }
        }
        R[k]=n;
        init_RMQ(k);
        for(int i=0;i<q;i++)
        {
            int l,r;
            scanf("%d%d",&l,&r);
            if(num[l]==num[r])
            {
                printf("%d
",r-l+1);
            }
            else
            {
                int ans1=max(R[num[l]]-l+1,r-L[num[r]]+1);
                int ans2=RMQ(num[l]+1,num[r]-1);
                printf("%d
",max(ans1,ans2));
            }
        }
    }
	return 0;
}