RMQ模板整理

查询区间的最大最小值，属于离线做法，主要运用倍增+DP思想。

参考书籍：算法进阶指南

一维RMQ

查询区间最大值或最小值

//求最大值,数组下标从1开始。

//求最小值,或者最大最小值下标,或者数组从0开始对应修改即可。

 const int MAXN = 50010;

int dp[MAXN][20];

int mm[MAXN];

//  初始化RMQ,b数组下标从1开始,b数组是区间元素序列

void initRMQ(int n, int b[])

{

    mm[0] = -1;

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

    {

        mm[i] = ((i & (i - 1)) == 0) ? mm[i - 1] + 1 : mm[i - 1];

        dp[i][0] = b[i];

    }

    for (int j = 1; j <= mm[n]; j++)

    {

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

        {

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

        }

    }

}



//  查询最大值

int rmq(int x, int y)

{

    int k = mm[y - x + 1];//int k= (int)(log((r - l + 1) * 1.0) / log(2.0));

    return max(dp[x][k], dp[y - (1 << k) + 1][k]);

}

二维RMQ

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int MAXN=255;
int val[MAXN][MAXN];
int dmin[MAXN][MAXN][8][8];
int dmax[MAXN][MAXN][8][8];
void initRMQ(int n,int m)
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            dmin[i][j][0][0]=dmax[i][j][0][0]=val[i][j];
    for(int ii=0;(1<<ii)<=n;ii++)
        for(int jj=0;(1<<jj)<=m;jj++)
        if(ii+jj)
            for(int i=1;i+(1<<ii)-1<=n;i++)
                for(int j=1;j+(1<<jj)-1<=m;j++)
                if(ii)
                {
                    dmin[i][j][ii][jj] = min(dmin[i][j][ii-1][jj] ,dmin[i+(1<<(ii-1))][j][ii-1][jj]);
                    dmax[i][j][ii][jj] = max(dmax[i][j][ii-1][jj] ,dmax[i+(1<<(ii-1))][j][ii-1][jj]);
                }
                else
                {
                    dmin[i][j][ii][jj] = min(dmin[i][j][ii][jj-1] , dmin[i][j+(1<<(jj-1))][ii][jj-1]);
                    dmax[i][j][ii][jj] = max(dmax[i][j][ii][jj-1] , dmax[i][j+(1<<(jj-1))][ii][jj-1]);
                }
}
int getMax(int x1,int y1,int x2,int y2)
{
    int k1=0;
    while((1<<(k1+1))<=x2-x1+1)k1++;
    int k2=0;
    while((1<<(k2+1))<=y2-y1+1)k2++;
    x2 = x2 - (1<<k1)+1;
    y2 = y2 - (1<<k2)+1;
    return max(max(dmax[x1][y1][k1][k2],dmax[x1][y2][k1][k2]) ,max(dmax[x2][y1][k1][k2],dmax[x2][y2][k1][k2]) );
}
int getMin(int x1,int y1,int x2,int y2)
{
    int k1=0;
    while((1<<(k1+1))<=x2-x1+1)k1++;
    int k2=0;
    while((1<<(k2+1))<=y2-y1+1)k2++;
    x2 = x2 - (1<<k1)+1;
    y2 = y2 - (1<<k2)+1;
    return min( min(dmin[x1][y1][k1][k2],dmin[x1][y2][k1][k2]) ,min(dmin[x2][y1][k1][k2],dmin[x2][y2][k1][k2]) );
}

int main()
{
    int n,b,k;
    while(scanf("%d%d%d",&n,&b,&k)==3&&n&&b&&k)
    {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                scanf("%d",&val[i][j]);
        initRMQ(n,n);
        while(k--)
        {
            int a,e;
            scanf("%d%d",&a,&e);
           int maxx= getMax(a,e,a+b-1,e+b-1);
           int minn= getMin(a,e,a+b-1,e+b-1);
           cout<<maxx-minn<<endl;
        }
    }
    return 0;
}