【Topic Link】

:point_right:Frequent values

【类别】

RMQ,游程编码

【题意】

给出一个非降序的整数数组，你的任务是对于一系列询问，回答区间内出现最多的值的次数.

【题解】

题目给的数组是非降序的.所有相等的元素都会聚集到一起。这样就可以把整个数组进行游程编码(Run Length Encoding,RLE).比如 (-1,1,1,2,2,2,4)就可以编码成(-1,1),(1,2),(2,3),(4,1),其中(a,b)表示有b个连续的a。用value[i]和count[i]分别表示第i段的数值和出现次数,num[p]、left[p]、right[p]、分别表示位置p所在段的编号和左右端点的位置.每次查询(L,R)的结果为以下三个部分的最大值:

1. 从L到L所在段的结束处的元素个数(right[L]-L+1)
2. 从R所在段开始到R的元素个数(R-left[R]+1)
3. 中间第num[L]+1段到第num[R]-1段的count的最大值,这一步是典型的RMQ问题,主要的时间也就花费在这里.
4. 特殊:如果L和R在同一个段中,则答案是R-L+1

【代码】

github:

1. :point_right:UVa 11235.cpp

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=100010;
vector<int> cnt;
int num[maxn],le[maxn],ri[maxn];
int dp[maxn][20];
int N,Q;

void RMQ_init(){
    int n=cnt.size();
    for(int i=0;i<n;++i) dp[i][0]=-cnt[i];
    ///2*(2^(j-1))=2^j
    ///dp(i,j)表示从i开始,长度为2^j的一段元素中的最小值.
    for(int j=1;(1<<j)<=n;++j)
        for(int i=0;i+(1<<j)-1<n;++i)
            dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}

int RMQ(int L,int R){
    if(L>R) return 0;
    int k=0;
    ///如果2^(k+1)<=R-L+1,那么k还可以加一
    while((1<<(k+1)<=R-L+1))k++;
    return min(dp[L][k],dp[R-(1<<k)+1][k]);
}

int main(){
    while(~scanf("%d",&N) && N){
        scanf("%d",&Q);
        cnt.clear();
        int pre=INF,ct=0;
        for(int i=0;i<N;++i){
            int numpy;
            scanf("%d",&numpy);
            if(numpy!=pre){
                pre=numpy;
                ct++;
                num[i]=ct-1;
                le[i]=i;
                if(i>=1)
                    for(int j=le[i-1];j<i;++j)
                        ri[j]=i-1;
                cnt.push_back(1);
            }else{
                num[i]=num[i-1];
                le[i]=le[i-1];
                cnt[ct-1]++;
            }
            if(i==N-1)
                for(int j=le[i];j<=i;++j)
                    ri[j]=i;
        }
/**
        for(int i=0;i<cnt.size();i++)
            cout<<i<<":"<<cnt[i]<<" ";
        cout<<endl;
        for(int i=0;i<N;i++)
            printf("%d(left,right,num):%d %d %d\n",i,le[i],ri[i],num[i]);
**/
        RMQ_init();
        for(int i=0;i<Q;++i){
            int a,b;
            scanf("%d%d",&a,&b);
            if(num[--a]==num[--b])
                printf("%d\n",b-a+1);
            else
                printf("%d\n",max(max((ri[a]-a+1),-RMQ(num[a]+1,num[b]-1)),(b-le[b]+1)));
        }
    }
    return 0;
}