题解 SP1684 【FREQUENT - Frequent values】

· · 题解

题目：

SP1684

题目难度：

普及+/提高-

孪生题目编号：

UVA11235

部分分写法：

\text{A naive algorithm may not run in time!}

所以部分分写法是朴素算法

极端朴素，暴力枚举统计什么的我也不太清楚毕竟上来就是冲着正解去的

正解：

算法：\text{RMQ +} 二分查找

对于这个给定序列，我们可以这样处理（以样例为例）：

这个应该很好做，一个 cnt，一个前缀和。

然后，对于每个区间 [L,R]，二分查找与之对应的l,r（L,R 以 5,10 为例）， l 表示 L 所在区块的右端，r 表示 R 所在区块的左端：

实际代码实现中，l,r 对应的是空隙左边那个数。

该区间中的答案有 3 种可能：

以上 3 种情况取 \max 值。

注意一下 l,r 的特判。

做完了。

代码：

#include<bits/stdc++.h>
using namespace std;
const int LOG=17;
int tot,n,q,a[100005],cnt[100005],presum[100005],Log[100005],f[100005][LOG+1],L,R;
int findL()//二分找l
{
    int Ll=1,Rr=tot,ans=0;
    while(Ll<=Rr)
    {
        int mid=(Ll+Rr)/2;
        if(presum[mid]<L)
            ans=mid,Ll=mid+1;
        else
            Rr=mid-1;
    }
//  printf("%d ",ans);
    return ans+1; //注意要+1,因为找到的是l的左边
}
int findR()//二分找r
{
    int Ll=1,Rr=tot,ans=0;
    while(Ll<=Rr)
    {
        int mid=(Ll+Rr)/2;
        if(presum[mid]<R)
            ans=mid,Ll=mid+1;
        else
            Rr=mid-1;
    }
//  printf("%d ",ans);
    return ans; 
}
int main()
{
    cin>>n;
    while(n!=0)//注意是多组数据！
    {
        tot=q=0;
        memset(a,0,sizeof(a));
        memset(cnt,0,sizeof(cnt));
        memset(f,0,sizeof(f));
        memset(presum,0,sizeof(presum));

        scanf("%d",&q);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            if(a[i]==a[i-1])
                cnt[tot]++;
            else
                cnt[++tot]++;//cnt的实现
        }
        Log[0]=-1;
        for(int i=1;i<=tot;i++)
            f[i][0]=cnt[i],Log[i]=Log[i>>1]+1,presum[i]=presum[i-1]+cnt[i];//cout<<cnt[i]<<" ";
            //presum的实现
        //cout<<endl;
        for(int j=1;j<=LOG;j++)
            for(int i=1;i+(1<<j)-1<=tot;i++)
                f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);//RMQ
        for(int i=1;i<=q;i++)
        {
            scanf("%d%d",&L,&R);
            int l=findL(),r=findR();
            if(l==r)
            {
                printf("%d\n",max(presum[l]-L+1,R-presum[r]));//特判1，注意个数是否要+-1，可以自己去画图思考。
                continue;
            }
            if(r<l)//特判2
            {
                printf("%d\n",R-L+1);
                continue;
            }
            int s=Log[r-l];
            //printf("%d %d %d\n",max(f[l+1][s],f[r-(1<<s)+1][s]),max(presum[l]-L+1,R-presum[r]),max(max(f[l+1][s],f[r-(1<<s)+1][s]),max(presum[l]-L+1,R-presum[r])));
            printf("%d\n",max(max(f[l+1][s],f[r-(1<<s)+1][s]),max(presum[l]-L+1,R-presum[r])));//注意是f[l+1]因为不含第l项
        }
        cin>>n;
    }
    return 0;
}