rmq_ST算法（矩阵最值）

已知某矩阵中的值已经确定，需求矩阵中某个小矩阵的最值

ST算法

我们可以将每一行看作一维的rmq

　maxx[i][j][k]表示： 第i行 [j,j+(1<<k)-1] 区间中的最大值
    maxx[i][j][k]=max(maxx[i][j][k-1],maxx[i][j+(1<<(k-1))][k-1]);
    该时间复杂度为:
        建表：0(n*m*log(m))
        查询：0(n)

模板：

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
const int N=1e3+7;
const int inf=1e9+7;
int n,m;
int maxx[N][N][13],minn[N][N][13];
int Log2[N];
void ST()
{
    for(int i = 0; i <= m; i ++)Log2[i] = (i == 0 ? -1 : Log2[i >> 1] + 1);
    for(int i=1;i<=n;i++)
        for(int k=1;k<13;k++)
            for(int j=1;j+(1<<k)<=m+1;j++)
            {
                maxx[i][j][k]=max(maxx[i][j][k-1],maxx[i][j+(1<<(k-1))][k-1]);
                minn[i][j][k]=min(minn[i][j][k-1],minn[i][j+(1<<(k-1))][k-1]);
            }
}
int query_min(int lx,int ly,int rx,int ry)
{
    int k=Log2[ry-ly+1];
    int minn1=inf;
    for(int i=lx;i<=rx;i++)
        minn1=min(minn1,min(minn[i][ly][k],minn[i][ry-(1<<k)+1][k]));
    return minn1;
}
int query_max(int lx,int ly,int rx,int ry)
{
    int k=Log2[ry-ly+1];
    int maxx1=-inf;
    for(int i=lx;i<=rx;i++)
        maxx1=max(maxx1,max(maxx[i][ly][k],maxx[i][ry-(1<<k)+1][k]));
    return maxx1;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&maxx[i][j][0]);
            minn[i][j][0]=maxx[i][j][0];
        }
    ST();
    int q;
    scanf("%d",&q);
    while(q--)
    {
        int lx,ly,rx,ry;
        scanf("%d%d%d%d",&lx,&ly,&rx,&ry);
        printf("%d %d
",query_max(lx,ly,rx,ry),query_min(lx,ly,rx,ry));
    }
    return 0;
}

poj 2019 Cornfields

二维rmq模板题：

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

const int N=250+7;
const int inf=15625000+7;
int n,minn[N][N][10],maxx[N][N][10],Log2[N];
void ST()
{
    for(int i=0;i<=n;i++) Log2[i]=(i==0?-1:Log2[i>>1]+1);
    for(int i=1;i<=n;i++)
        for(int k=1;k<10;k++)
            for(int j=1;j+(1<<k)<=n+1;j++)
            {
                minn[i][j][k]=min(minn[i][j][k-1],minn[i][j+(1<<(k-1))][k-1]);
                maxx[i][j][k]=max(maxx[i][j][k-1],maxx[i][j+(1<<(k-1))][k-1]);
            }
}
int query_min(int lx,int ly,int rx,int ry)
{
    int minn1=inf;
    int k=Log2[ry-ly+1];
    for(int i=lx;i<=rx;i++)
        minn1=min(minn1,min(minn[i][ly][k],minn[i][ry-(1<<k)+1][k]));
    return minn1;
}
int query_max(int lx,int ly,int rx,int ry)
{
    int maxx1=-inf;
    int k=Log2[ry-ly+1];
    for(int i=lx;i<=rx;i++)
        maxx1=max(maxx1,max(maxx[i][ly][k],maxx[i][ry-(1<<k)+1][k]));
    return maxx1;
}
int main()
{
    int b,k;
    scanf("%d%d%d",&n,&b,&k);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            scanf("%d",&minn[i][j][0]);
            maxx[i][j][0]=minn[i][j][0];
        }
    ST();
    while(k--)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%d
",query_max(x,y,x+b-1,y+b-1)-query_min(x,y,x+b-1,y+b-1));
    }
    return 0;
}