首页 > 代码库 > UVA 11235 RMQ算法

UVA 11235 RMQ算法

2024-07-07 23:24:56   225人阅读

上次的湘潭赛的C题，用线段树敲了下还是WA，不知道为何，我已经注意了处理相同数据，然后他们当时用的RMQ。

所以学了下RMQ，感觉算法思想是一样的，RMQ用了DP或者是递推，由单个数到2^k往上推，虽然有部分重叠的，也没关系，因为RMQ是求区间最值嘛

然后这道题目，要把出现次数化为最值，构造一个新的数组来存贮出现次数，每次是在这个数组里面查询。细节处理要注意，比如所求的区间可能就在一个段里面，需要单独判断。

#include <iostream>
#include <cstdio>
#include <vector>
#define N 100010
using namespace std;
int n,q;
int A[N],num[N],lefts[N],rights[N];
int d[N][20];
void RMQ_init(const vector<int>& a)
{
    int s=a.size();
    for (int i=0;i<s;i++) d[i][0]=a[i];
    for (int j=1;(1<<j)<=n;j++){
        for (int i=0;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()
{
    while (scanf("%d",&n))
    {
        if (!n) break;
        scanf("%d",&q);
        vector<int> tmp;
        int st=0;
        for (int i=0;i<n;i++)scanf("%d",&A[i]);
        A[n]=A[n-1]+1;
        for (int i=1;i<=n;i++){
            if (A[i]!=A[i-1]){
                tmp.push_back(i-st);
                for (int j=st;j<i;j++){
                    num[j]=tmp.size()-1;
                    lefts[j]=st;
                    rights[j]=i-1;
                }
                st=i;
            }
        }
        RMQ_init(tmp);
        int L,R;
        while (q--)
        {
            scanf("%d%d",&L,&R);
            L--;R--;
            int ans;
            if (num[L]==num[R]) ans=R-L+1;
            else{
             ans=max(R-lefts[R]+1,rights[L]-L+1);
             if (num[L]+1<num[R]){
                ans=max(ans,RMQ(num[L]+1,num[R]-1));
             }
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}

 


联系
我们