题解 UVA11235 【Frequent values】

2018-05-08 10:21:06


可以注意到,题目中说,这是个非降序序列,也就是说,所有相同的数都是连在一起的!!

所以我们可以把原序列分段,比如样例:-1 -1 1 1 1 1 3 10 10 10

我们可以这样记录:我们把所有相同的数归成一段。用num[p]来记录p这个位置在第几段里,比如num[1]=1,num[2]=1,num[3]=2。然后用l[i]来记录第i段的左边界的序号,r[i]来记录第i段的右边界的序号,比如l[2]=3,r[2]=6。

然后,我们对于每个询问l,r,只需要把l,r分成三个部分求,像这样:

然后就转化为了求RMQ,于是我喜欢ST表,于是代码如下。。。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,cnt=0;
int num[500000],l[500000],r[500000],val[500000];
int f[20][500000];
void Clear()
{
    cnt=0;
    memset(l,0,sizeof(l));
    memset(r,0,sizeof(r));
    memset(f,0,sizeof(f));
    memset(num,0,sizeof(num));
    memset(val,0,sizeof(val));
}
int main()
{
    while(1)
    {
        Clear();
        scanf("%d",&n);
        if(!n) break;
        scanf("%d",&m);
        int tmp=-1123645162;//这是乱打的,只要保证第一个x不等于tmp就行。。
        for(int i=1;i<=n;i++)
        {
            int x;
            scanf("%d",&x);
            if(x!=tmp) r[cnt]=i-1,l[++cnt]=i,tmp=x;
            num[i]=cnt;//处理各个数组
        }
        for(int i=1;i<=cnt;i++)
            f[0][i]=r[i]-l[i]+1;//预处理f数组
        for(int i=1;(1<<i)<=cnt;i++)
            for(int j=1;j<=n-(1<<i)+1;j++)
                f[i][j]=max(f[i-1][j],f[i-1][j+(1<<(i-1))]);
        //ST表求RMQ
        for(int i=1;i<=m;i++)
        {  
            int x,y;
            scanf("%d%d",&x,&y);
            if(x>y) swap(x,y);
            if(num[x]==num[y]) printf("%d\n",y-x+1);//如果刚好在一段里,那么直接减一下输出
            else  
            {  
                int ans=0;  
                if(num[x]+1<=num[y]-1)
                {
                    int L=num[x]+1,R=num[y]-1;
                    int k=0;  
                    while((1<<(k+1))<=R-L+1) k++;  
                    ans=max(f[k][L],f[k][R-(1<<k)+1]);
                }
                ans=max(ans,max(r[num[x]]-x+1,y-l[num[y]]+1));  
                //在三段中取最大
                printf("%d\n",ans);  
            }  
        }
    }
    return 0;
}