POJ 3368 Frequent Values(RMQ，需要轉換)

題意：

給一非遞減數組，求區間[L,R]中出現次數最多的值所出現的次數。           

藍書P198有詳細分析。

題解：

            遊程編碼：（a,b）表示有b個連續的a。

比如-1,1,1,2,2,2,4可以這樣表示：

(-1,1),(1,2),(2,3),(4,1)。需要用一些的數組記錄！具體看代碼注釋。

然後求一個區間最大的b就可以了，區間兩邊需要單獨處理。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int maxn = 200000+1111;

int dmax[maxn][20];
int a[maxn];//原始資料
int Left[maxn],Right[maxn],num[maxn],d[maxn];

void initmax(int n,int d[])
{
    for(int i=1;i<=n;i++)
       dmax[i][0] = d[i];
    for(int j=1;(1<<j)<=n;j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
          dmax[i][j]=max(dmax[i][j-1],dmax[i+(1<<(j-1))][j-1]);
}

int getmax(int l,int r)
{
    int k=0;
    while(1<<(k+1)<=r-l+1)k++;
    return max(dmax[l][k],dmax[r+1-(1<<k)][k]);
}

int main()
{
    int n,q;
    while(cin>>n&&n)
    {
        memset(d,0,sizeof d);
        cin>>q;
        cin>>a[1];
        int cnt=1;//不同值的種數
        Left[cnt]=1;//第cnt段最左邊的位置是1
        Right[cnt]=1;//第cnt段最右邊的位置是1
        d[cnt]=1;//第cnt段有1個元素
        num[1]=cnt;//第1個元素是屬于第cnt段
        for(int i=2;i<=n;i++)
        {
            scanf("%d",a+i);
            if(a[i]==a[i-1])///一段連續的
            {
                num[i]=cnt;
                Right[cnt]=i;
                d[cnt]++;
            }
            else///出現新的
            {
                num[i]=++cnt;
                Right[cnt]=Left[cnt]=i;
                d[cnt]=1;
            }
        }
        initmax(n,d);
        while(q--)
        {
            int l,r;
            scanf("%d%d",&l,&r);
            int numl=num[l],numr=num[r];
            if(numl==numr)
                printf("%d\n",r-l+1);
            else
            {
                int q = Right[num[l]]-l+1;///左邊連續有幾個
                int w = r - Left[num[r]]+1;///右邊連續有幾個
                int e=0;
                if(numr-numl>1)
                    e=getmax(numl+1,numr-1);///中間最多的有多少個
                int ans=max(e,max(q,w));
                printf("%d\n",ans);
            }
        }
    }
}