uva 11235 RMQ范围最大值

题目大意：给一个整数上升序列，对于一系列询问区间（i，j），回答这段区间出现次数最多值所出现的次数。

分析：一个上升序列，相同的值聚集在一起，把相同的值的区间看作一个整体，假设这样的整体有n个，把他们编号。

num[p]表示原下标下的数所在段的编号，left[p]、right[p]表示所在段原下标的左右端点位置。编号后的数组

用RMQ求范围最大值。对于询问的区间（L,R）在编号后的数组中以以下三个部分的最大值：从L到L所在段的结束处

的元素个数（即right[L]-L+1）、从R所在段的开始处到R处的元素的个数（即R-left[R]+1）、中间第num[L]+1段

到num[R]-1段的最大值（用RMQ）。

特殊情况：L、R在同一段中，则答案为R-L+1。

#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;

const int maxn=100005;
const int maxm=20;

inline int max(int a,int b){ return a>b?a:b;}

struct RMQ
{
    int d[maxn][maxm];
    void init(const vector<int> &A)
    {
        int n=A.size(),i,j;
        for(i=0;i<n;i++) d[i][0]=A[i];
        for(j=1;(1<<j) <= n;j++)
        for(i=0;i+(1<<j)-1<n;i++)
            d[i][j]=max(d[i][j-1],d[i+(1<<(j-1))][j-1]);
    }
    int query(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]);
    }
}rmq;

int a[maxn],num[maxn],Left[maxn],Right[maxn];

int main()
{
    int n,q,i,j,R,L,start,ans;
    vector<int> count;
    while(scanf("%d %d",&n,&q)==2)
    {
        for(i=0;i<n;i++) scanf("%d",a+i);
        a[n]=a[n-1]+1;
        start=-1;
        count.clear();
        for(i=0;i<=n;i++)
        {
            if(i==0 || a[i]>a[i-1])
            {
                if(i>0)
                {
                    count.push_back(i-start);
                    for(j=start;j<i;j++)
                    {
                        num[j]=count.size()-1;Left[j]=start;Right[j]=i-1;
                    }
                }
                start=i;
            }
        }
        rmq.init(count);
        while(q--)
        {
            scanf("%d %d",&L,&R);
            L--;R--;
            if(num[L] == num[R]) ans=R-L+1;
            else
            {
                ans=max(Right[L]-L+1,R-Left[R]+1);
                if(num[L]+1 < num[R]) ans=max(ans,rmq.query(num[L]+1,num[R]-1));
            }
            printf("%d
",ans);
        }
    }
    return 0;
}

uva 11235 RMQ范围最大值

相关推荐