[数据结构]RMQ问题小结

RMQ问题小结

　　by Wine93 2014.1.14

1.算法简介

RMQ问题可分成以下2种

(1)静态RMQ:ST算法

一旦给定序列确定后就不在更新,只查询区间最大(小)值!这类问题可以用倍增的ST算法进行预处理

预处理:O(nlogn)

查询:O(1)

(2)动态RMQ:线段树

要更新一些值,还有询问

更新:O(logn)

查询:O(logn)

2.相关题目

(1)静态RMQ

1.POJ 3264 Balanced Lineup(一维静态RMQ模板题) http://poj.org/problem?id=3264

题意:给定n(n<=50000)个数字,每次询问[l,r]内的最大值和最小值差

分析:裸的一维RMQ,用ST预处理!

# include<cstdio>

# include<cstring>

# include<algorithm>

using namespace std;

# define N 

int log2[N];

int a[N],f[N][],g[N][];

//f:max g:min

void initRMQ(int a[],int n)

{

    int i,j;

    log2[]=;

    for(i=;i<N;i++)

        log2[i]=log2[i-]+!(i&(i-));

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

        f[i][]=g[i][]=a[i];

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

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

        {

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

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

        }

}

int getmax(int l,int r)

{

    int k=log2[r-l+];

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

}

int getmin(int l,int r)

{

    int k=log2[r-l+];

    return min(g[l][k],g[r-(<<k)+][k]);

}

int main()

{

    int i,n,m,x,y;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

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

            scanf("%d",&a[i]);

        initRMQ(a,n);

        for(i=;i<=m;i++)

        {

            scanf("%d%d",&x,&y);

            printf("%d\n",getmax(x,y)-getmin(x,y));

        }

    }

    return ;

}

POJ 3264

2.HDU 2888 Check Corners(二维静态RMQ模板题) http://acm.hdu.edu.cn/showproblem.php?pid=2888

题意:给定一个n*m (1<=m,n<=300)的矩阵!每次询问(r1，c1)为左上角,(r2,c2)为右下角的子矩形的最大值。

分析:裸的二维RMQ,用ST预处理即可!

# include<cstdio>

# include<cstring>

# include<algorithm>

using namespace std;

# define N

# define M

int dp[N][N][M][M];

int log2[N];

int a[N][N],n,m,q;

void initRMQ()

{

    int i,j,k,l;

    for(k=;(<<k)<=n&&k<=;k++)

        for(l=;(<<l)<=m&&l<=;l++)

            for(i=;i+(<<k)-<=n;i++)

                for(j=;j+(<<l)-<=m;j++)

                {

                    if(k==&&l==) dp[i][j][k][l]=a[i][j];

                    else if(k==) dp[i][j][k][l]=max(dp[i][j][k][l-],dp[i][j+(<<l-)][k][l-]);

                    else if(l==) dp[i][j][k][l]=max(dp[i][j][k-][l],dp[i+(<<k-)][j][k-][l]);

                    else

                    {

                        int a=max(dp[i][j][k-][l-],dp[i][j+(<<l-)][k-][l-]);

                        int b=max(dp[i+(<<k-)][j][k-][l-],dp[i+(<<k-)][j+(<<l-)][k-][l-]);

                        dp[i][j][k][l]=max(a,b);

                    }

                }

}

int getmax(int x1,int y1,int x2,int y2)

{

    int k=log2[x2-x1+];

    int l=log2[y2-y1+];

    int a=max(dp[x1][y1][k][l],dp[x2-(<<k)+][y1][k][l]);

    int b=max(dp[x1][y2-(<<l)+][k][l],dp[x2-(<<k)+][y2-(<<l)+][k][l]);

    return max(a,b);

}

int main()

{

    int i,j,x1,y1,x2,y2;

    log2[]=;

    for(i=;i<N;i++)

        log2[i]=log2[i-]+!((i-)&i);

    while(scanf("%d%d",&n,&m)!=EOF)

    {

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

            for(j=;j<=m;j++)

                scanf("%d",&a[i][j]);

        initRMQ();

        scanf("%d",&q);

        while(q--)

        {

            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

            int ans=getmax(x1,y1,x2,y2);

            int res=max(max(a[x1][y1],a[x1][y2]),max(a[x2][y1],a[x2][y2]));

            printf("%d ",ans);

            if(res==ans) printf("yes\n");

            else printf("no\n");

        }

    }

    return ;

}

HDU 2888

3.LightOJ 1081 Square Queries(二维静态RMQ降维) http://www.lightoj.com/volume_showproblem.php?problem=1081

题意:给定一个n*n(n<=500)的矩阵!每次询问以(x,y)为左上角,边长为l的正方形区域内的最大值

分析:如果用一般的二维RMQ预处理,时间复杂度为n*n*logn*logn(约2000万),会超时!因为查询区域为正方形,我们只要每次都存储正方形就行了!

Max[i][j][k]:以(i,j)为左上角,边长为2^k区域内的最大值,每次倍增把大正方形拆成4个小正方形即可!

# include<map>

# include<set>

# include<cmath>

# include<queue>

# include<stack>

# include<vector>

# include<string>

# include<cstdio>

# include<cstring>

# include<iostream>

# include<algorithm>

# include<functional>

using namespace std;

typedef pair<int,int> PII;

# define MOD

# define LL long long

# define pb push_back

# define F first

# define S second

# define N

# define M

int Max[N][N][M],Log2[N];

int a[N][N];

void initLog()  //初始化Log2数组

{

    int i;

    Log2[]=-;

    for(i=;i<N;i++)

        Log2[i]=Log2[i-]+!(i&i-);

}

void initRMQ(int n)

{

    int i,j,k,lu,ld,ru,rd;

    for(k=;(<<k)<=n;k++)

        for(i=;i+(<<k)-<=n;i++)

            for(j=;j+(<<k)-<=n;j++)

            {

                if(k==) Max[i][j][k]=a[i][j];

                else

                {

                    lu=Max[i][j][k-];   //左上角

                    ld=Max[i+(<<k-)][j][k-];  //左下角

                    ru=Max[i][j+(<<k-)][k-];  //右上角

                    rd=Max[i+(<<k-)][j+(<<k-)][k-];  //右下角

                    Max[i][j][k]=max(max(lu,ld),max(ru,rd));

                }

            }

}

int Query(int x,int y,int l)

{

    if(l==) return a[x][y]; //注意

    int k=Log2[l];

    int lu=Max[x][y][k];

    int ld=Max[x+l-(<<k)][y][k];

    int ru=Max[x][y+l-(<<k)][k];

    int rd=Max[x+l-(<<k)][y+l-(<<k)][k];

    return max(max(lu,ld),max(ru,rd));

}

int main()

{

    //freopen("in.txt","r",stdin);

    initLog();

    int cas,T,i,j,n,m,x,y,l;

    scanf("%d",&T);

    for(cas=;cas<=T;cas++)

    {

        scanf("%d%d",&n,&m);

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

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

                scanf("%d",&a[i][j]);

        initRMQ(n);

        printf("Case %d:\n",cas);

        while(m--)

        {

            scanf("%d%d%d",&x,&y,&l);

            printf("%d\n",Query(x,y,l));

        }

    }

    return ;

}

Lightoj 1081

4.POJ 3368 Frequent values

题意:给定n(n<=100000)个数,每次询问一个区间内重复数字的最大次数

5.POJ 2452 Sticks Problem

6.HDU 3486 Interviewe

(2)动态RMQ

1.HDU 1754 I Hate It (一维动态RMQ模板题)

2.Uva 11297 Census(二维动态RMQ模板题)

3.HDU 4819 Mosaic (13年长春现场)

4.NBU 2475 Survivors
5.BUAA 724 晴天小猪的神题

巴特西

[数据结构]RMQ问题小结

最新文章

热门文章