UVA 11235-Frequent values（RMQ）

浅浅的花香味﹌ 2022-07-19 02:00 89阅读 0赞

**Frequent values**

![20160808170630404][]

## 题目意思： ##

给出一个非降序排列的整数数组A，对于一系列询问（L,R），求出AL~AR区间内出现次数最多的值出现的次数。

## 解题思路： ##

数组非降序，所以对整个数组进行游程编码。

所求的最大值是以下三个部分的最大值：

①从L到L所在的段的结束处的元素个数：right\[L\]-L+1

②从R到R所在的段的开始处的元素个数：R-left\[R\]+1

③中间第num\[L\]+1段到第num\[R\]-1段的cnt的最大值(RMQ)

注意！！这题输入输出要用C风格，C++会RE…Orz

#include <iostream>
    #include <algorithm>
    #include <cstring>
    #include <cstdio>
    #define maxn 100100
    #define ll long long
    using namespace std;
    int n,m;
    int a[maxn],d[maxn][50];//给定的数组个RMQ用的DP数组
    int value[maxn],cnt[maxn];//第i段的数值和出现次数
    int num[maxn],lefts[maxn],rights[maxn];//当前下标表示的位置的所在段的编号和左右端点的位置
    void RMQ_init()
    {
        int i,j;
        for(i=1; i<=n; i++)
            d[i][0]=cnt[i];
        for(j=1; (1<<j)<=n; j++)
            for(i=1; i+(1<<j)-1<=n; i++)
                d[i][j]=max(d[i][j-1],d[i+(1<<(j-1))][j-1]);
    }
    
    int RMQ(int l,int r)
    {
        int k=0;
        while((1<<(k+1))<=r-l+1) k++;
        return max(d[l][k],d[r-(1<<k)+1][k]);
    }
    
    
    int main()
    {
    #ifdef ONLINE_JUDGE
    #else
        freopen("G:/x/read.txt","r",stdin);
        freopen("G:/x/out.txt","w",stdout);
    #endif
        int q,i,m=1,l,ans=-1;
        bool flag=false;
        while(scanf("%d",&n),n)
        {
            scanf("%d",&q);
            memset(a,0,sizeof(a));
            memset(value,0,sizeof(value));
            memset(cnt,0,sizeof(cnt));
            memset(num,0,sizeof(num));
            memset(lefts,0,sizeof(lefts));
            memset(rights,0,sizeof(rights));
            memset(d,0,sizeof(d));
            for(i=1; i<=n; ++i)
            {
                scanf("%d",&a[i]);
                if(a[i]!=a[i-1]&&i!=1) flag=true;
                if(i==1)//a[1]特判一下
                {
                    value[m]=a[i];
                    ++cnt[m];
                    num[i]=m;
                    lefts[i]=i;
                    l=i;
                }
                if(flag&&i!=1)
                {
                    lefts[i]=i;
                    l=i;
                    ++m;
                    num[i]=m;
                    value[m]=a[i];
                    ++cnt[m];
                    for(int k=lefts[i-1]; k<i; ++k)
                        rights[k]=i-1;
                    flag=false;
                }
                else
                {
                    if(i!=1)
                    {
                        ++cnt[m];
                        num[i]=m;
                        lefts[i]=l;
                        value[m]=a[i];
                    }
                    if(i==n)
                        for(int k=lefts[i-1]; k<=i; ++k)
                            rights[k]=i;
                }
            }
            RMQ_init();
            for(i=0; i<q; ++i)
            {
                int l,r;
                scanf("%d%d",&l,&r);
                if(num[l]==num[r])  printf("%d\n",r-l+1);//特判，如果L和R在同一段中
                else
                {
                    ans=max((rights[l]-l+1),(r-lefts[r]+1));
                    if(num[l]+1<=num[r]-1)//必须保证RMQ区间左端点小于右端点
                    {
                        int res=RMQ(num[l]+1,num[r]-1);
                        ans=max(ans,res);
                    }
                    printf("%d\n",ans);
                }
            }
        }
        return 0;
    }
    /**
    10 3
    -1 -1 1 1 1 1 3 10 10 10
    2 3
    1 10
    5 10
    0
    **/

[20160808170630404]: /images/20220718/124d1bfd3f3c4a1b83bcf7a12e2576c8.png