POJ3368-Frequent values(RMQ-ST)

Frequent values

题意：

给出一串非递减序列，询问区间中出现次数最多的数的次数是多少？

思路：

• 非递减序列，意味着相同的数会连在一起。
• 用一个数组cnt记录当前数字个数
• 比如样例1：-1 -1 1 1 1 1 3 10 10 10 cnt数组存储：1 2 1 2 3 4 1 1 2 3 表示当前元素出现的次数。 这样我每次求区间次数最大值，就是对cnt数组求解区间最大值。现在询问区间[1 10]，显而易见是4，在这段区间数字1出现了4次； 那假如是[5 10]呢，这段区间的cnt数组为3 4 1 1 2 3 这个时候答案就不能是4了，1只出现了两次，而10出现了三次。

• 那我们要怎么处理这个情况呢？

• 我们知道之所以会出现这种情况是因为询问区间将一个连续的数字在中间截断了，但是后面的区间的最大值不会收到影响，只会影响左端截断的序列，那我们可以将开头截断的部分单独拿出来，后面完整的序列按照第一步方法查找最大值。所以对于开头部分的元素，我们要另外再处理一下，要先将这个区间里第一个元素的个数求出来，再求剩下区间的最大值。所以对于区间[5 10]，先找出第一个元素的个数发现是两个，再对剩下的区间[7 10]求最大值，发现是三个。所以最后答案就是3。再两者比较去最大值。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int num[100010];
int cnt[100010];
int dpmaix[100010][25];
int n,q,x,y;
void ST(int n)
{
    for(int i=1;i<=n;i++)
    {
        dpmaix[i][0]=cnt[i];
    }
    for(int j=1;j<=24;j++)
    {
        for(int i=1;i+(1<<j)-1<=n;i++)
        {
            dpmaix[i][j]=max(dpmaix[i][j-1],dpmaix[i+(1<<(j-1))][j-1]);
        }
    }
}
int query(int i,int j)
{
    int k=log2(j-i+1.0);
    return max(dpmaix[i][k],dpmaix[j-(1<<k)+1][k]);
}
int main( )
{
    while(~scanf("%d%d",&n,&q)&&n)
    {
        for(int i=1;i<=n;i++)
        {
            cnt[i]=0;
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&num[i]);
            if(i==1)
            {
                cnt[i]=1;
            }
            else if(num[i]==num[i-1])
            {
                cnt[i]=cnt[i-1]+1;
            }
            else
            {
                cnt[i]=1;
            }  
        }
        ST(n);
        while(q--)
        {
            scanf("%d%d",&x,&y);
            int now=x;
            while(now<=y&&num[now-1]==num[now])//裁剪左端
            {
                now++;
            }
            int ans=0;
            if(now<=y)
            {
                ans=query(now,y);//寻找完整右端
            }
            ans=max(ans,now-x);
            printf("%d\n",ans);
        }
    }
    return 0;
}