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

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

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

rmq[r1+1][log2(r2-1-r1)],

rmq[r2-p2[log2(r2-1-r1)]][log2(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;
}
分类: 文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *