RMQ算法以及UVA 11235 Frequent Values(RMQ)

RMQ算法

简单来说，RMQ算法是给定一组数据，求取区间[l,r]内的最大或最小值。

例如一组任意数据 5 6 8 1 3 11 45 78 59 66 4，求取区间(1,8) 内的最大值。数据量小时，只需遍历一遍就可以，数据量一大时就容易时间超限，RMQ算法是一种高效算法，和线段树差不多（当没有数据的实时更新时），当然两者都需要预处理。

定义映射f(i,j)=x,即以i为起点，长度为2^j区间内的最大最小值，显而易见f(i,0)为该数本身，那么求f(i,j+1)时；

可得公式 f(i,j)=max(f(i,j-1),f(i+(1<<j-1),j-1) 即f(1,2)=max(f(1,0),f(2,0))=6;

代码如下：

void get_RMQ()

{

    for(int i=;i<=n;i++)

    {

        scanf("%d",&x);

        maxx[i][]=x;

        minx[i][]=x;

    }

    for(int j=;(<<j)<=n;j++)

    {

        for(int i=;i+(<<j)<=n;j++)

        {

            maxx[i][j]=max(maxx[i][j-],maxx[i+(<<(j-))][j-]);

            minx[i][j]=min(minx[i][j-],minx[i+(<<(j-))][j-]);

        }

    }

}

例题 UVA 11235 Frequent Values(RMQ)

You are given a sequence of n integers a₁ , a₂ , ... , a_n in non-decreasing order. In addition to that, you are given several queries consisting of indices i and j (1 ≤ i ≤ j ≤ n). For each query, determine the most frequent value among the integers a_i , ... , a_j.

Input Specification

The input consists of several test cases. Each test case starts with a line containing two integers n and q(1 ≤ n, q ≤ 100000). The next line contains n integers a₁ , ... , a_n (-100000 ≤ a_i ≤ 100000, for each i ∈ {1, ..., n}) separated by spaces. You can assume that for each i ∈ {1, ..., n-1}: a_i ≤ a_i+1. The following q lines contain one query each, consisting of two integers i and j (1 ≤ i ≤ j ≤ n), which indicate the boundary indices for the query.

The last test case is followed by a line containing a single 0.

Output Specification

For each query, print one line with one integer: The number of occurrences of the most frequent value within the given range.

Sample Input

10 3

-1 -1 1 1 1 1 3 10 10 10

2 3

1 10

5 10

0

Sample Output

1

4

3
题目大意，给定一个非降序数列，求给定区间内出现的某个数出现的最大重复次数。
RMQ思路：
    因为非降序，所以-1记为第一个数，出现了两次，然后lx[1]记录原数组内-1出现的首位置，rx[1]记录原数组内-1最后出现的位置ans[i]=tot,即ans[1]=ans[2]=1，
则原数组转化为2，4，1，3；查询l,r时先判断ans[l]是否等于ans[r] 若ans[l]==ans[r] 则说明 区间(l,r)内都是同一个数，所以结果为r-l+1;
否则 result=max(RMQ(ans[l]+1,ans[r]-1),max(r-lx[ans[r]]+1,rx[ans[l]]-l+1)；因为断点处无法准确判断所以单独考虑。
RMQ代码如下 时间：540ms

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int mod=1e5+;

int ans[mod],pos[mod],lx[mod],rx[mod];

int dp[mod][],tot,x,n,q,l,r,last;

int max(int x,int y){

    return x>y?x:y;

}

void get_RMQ()//dp预处理

{

    for(int i=;i<=tot;i++){

        dp[i][]=pos[i];

    }

    for(int j=;(<<j)<=tot;j++)

    {

        for(int i=;i+(<<j)-<=tot;i++)

        {

            dp[i][j]=max(dp[i][j-],dp[i+(<<(j-))][j-]);

        }

    }

}

int RMQ(int l,int r)//查询

{

    if(l>r) return ;

    int k=;

    while(<<(+k)<=r-l+)k++;

    return max(dp[l][k],dp[r-(<<k)+][k]);

}

int main()

{

    while(~scanf("%d",&n)&&n)

    {

        scanf("%d",&q);

        tot=;

        memset(dp,,sizeof(dp));

        memset(ans,,sizeof(ans));

        memset(pos,,sizeof(pos));

        memset(lx,,sizeof(lx));

        memset(rx,,sizeof(rx));

        for(int i=;i<=n;i++)

        {

            scanf("%d",&x);

            if(i==){last=x;++tot;lx[tot]=;}

            if(x==last){ans[i]=tot;pos[tot]++;rx[tot]++;}

            else {ans[i]=++tot;pos[tot]++;lx[tot]=rx[tot]=i;last=x;}

        }

        get_RMQ();

        while(q--)

        {

            scanf("%d%d",&l,&r);

            if(ans[l]==ans[r]) printf("%d\n",r-l+);

            else printf("%d\n",max(RMQ(ans[l]+,ans[r]-),max(rx[ans[l]]-l+,r-lx[ans[r]]+)));

            //端点处单独考虑

        }

    }

    return ;

}

再来一个线段树代码，时间：730ms

//线段树查询

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

const int mod=1e5+;

int node[mod*],ans[mod],pos[mod],lx[mod],rx[mod];

int last,x,n,q,r,l,tot,cont;

int max(int x,int y){

    return x>y?x:y;

}

void PushUp(int t){

        node[t]=max(node[t<<],node[(t<<)+]);

}

void build(int l,int r,int t){//建造线段树

    int mid;

    mid=(l+r)>>;

    if(l==r){

        node[t]=pos[++cont];//注意数据的导入，并不是与t相等

        return;

    }

    build(l,mid,t<<);

    build(mid+,r,(t<<)+);

    PushUp(t);

}

int query(int ll,int rr,int l,int r,int t){//区间查询

    int k=;

    int mid=(l+r)>>;

    if(ll<=l && rr>=r) return node[t];

    if(ll<=mid) k=max(k,query(ll,rr,l,mid,t<<));

    if(rr>mid) k=max(k,query(ll,rr,mid+,r,(t<<)+));

    return k;

}

int main(){

    while(~scanf("%d",&n)&&n){

        scanf("%d",&q);

        tot=;

        memset(ans,,sizeof(ans));

        memset(lx,,sizeof(lx));

        memset(rx,,sizeof(rx));

        memset(pos,,sizeof(pos));

        for(int i=;i<=n;i++){

            scanf("%d",&x);

            if(i==){last=x;++tot;lx[tot]=;}

            if(x==last){ans[i]=tot;pos[tot]++;rx[tot]++;}//数据的整合

            else {ans[i]=++tot;pos[tot]++;lx[tot]=rx[tot]=i;last=x;}

        }

        cont=;

        build(,tot,);

        while(q--){

            scanf("%d%d",&l,&r);

            if(ans[l]==ans[r]) printf("%d\n",r-l+);

            else printf("%d\n",max(query(ans[l]+,ans[r]-,,tot,),max(r-lx[ans[r]]+,rx[ans[l]]-l+)));

            //同样，端点处单独考虑

        }

    }

    return ;

}

巴特西

RMQ算法以及UVA 11235 Frequent Values(RMQ)

Input Specification

Output Specification

Sample Input

Sample Output

最新文章

热门文章

巴特西

RMQ算法 以及UVA 11235 Frequent Values(RMQ)

Input Specification

Output Specification

Sample Input

Sample Output

最新文章

热门文章

RMQ算法以及UVA 11235 Frequent Values(RMQ)