【题解】【RMQ】Frequent values(UVa11235)-boshi

题意：给定一组长度为 n 的不降序列，及 q 个询问 [l,r]。求 [l,r] 中出现最多的数出现了几次。

分析：把相同的数（肯定是连续的）分组，记录每组有几个数、结尾的数字是原数组第几位、每组包括的数是什么。在同时记录下原数组的每个数对应第几组。这些工作在 O(N) 的时间内完成。然后通过预处理，rmq[j][i] 保存从第 j 组开始 2ⁱ 组内出现最多的数是什么。rmq[j][i]=max(rmq[j][i-1],rmq[j+2^i-1][i-1]);

对于每次询问 [l,r]。如果 l、r 在同一组，max=r-l+1. 如果 l、r 不在同一组，则最大值在一下四个数内:(r1 为 l 所在的组，r2 为 r 所在的组)

rmq[r1+1][log₂(r2-1-r1)],

rmq[r2-p2[log₂(r2-1-r1)]][log₂(r2-1-r1)],

fns[r1]-l+1,

r-fns[r2-1]。

取最大值即可

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

#define MX 100001

using namespace std;

int cnt[MX];    //每一组数有几个
int fns[MX];    //每一组最后一个数是第几位上的
int num[MX],src[MX];    //每一组都是什么数、原数组
int rmq[MX][20];    //rmq 数组
int rag[MX];    //每一个数在第几组
int n,q,rnum;
int p2[18]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072}; //二的幂

int input()
{
    scanf("%d%d",&n,&q);
    if(n==0)return 0;
    for(int i=1;i<=n;i++)scanf("%d",&src[i]);
    return 1;
}

int query()
{
    int l,r,r1,r2,m1=0,m2=0,m3,m4;
    scanf("%d%d",&l,&r);
    if(rag[l]==rag[r])return r-l+1;
    else
    {
        r1=rag[l];
        r2=rag[r];
        if(r2-1-r1>0)m1=rmq[r1+1][(int)log2(r2-1-r1)],m2=rmq[r2-p2[(int)log2(r2-1-r1)]][(int)log2(r2-1-r1)];
        m3=fns[r1]-l+1;
        m4=r-fns[r2-1];
        return max(max(m1,m2),max(m3,m4));
    }
    return 0;
}

void make()
{
    int now=1,p=0;
    for(int i=1;i<=n;i++)rag[i]=1;
    for(int i=2;i<=n+1;i++)
    {
        if(src[i]==src[i-1])now++;
        else
        {
            cnt[++p]=now;
            rmq[p][0]=now;
            num[p]=src[i-1];
            now=1;
            fns[p]=i-1;
        }
        rag[i]=p+1;
    }
    rnum=p;
    for(int i=1;(1<<(i-1))<=rnum;i++)for(int j=1;j<=rnum;j++)rmq[j][i]=max(rmq[j][i-1],rmq[j+(1<<(i-1))][i-1]);
}

int main()
{
    while(input())
    {
        make();
        for(int i=1;i<=q;i++)cout<<query()<<endl;
    }
    return 0;
}