poj2019 二维RMQ模板题

时间：2021-02-27 19:37:42

和hdu2888基本上一样的，也是求一个矩阵内的极值

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<cmath>

using namespace std;

#define maxn 252

int n,b,q;

int dpmax[maxn][maxn][][],dpmin[maxn][maxn][][],val[maxn][maxn];

void ST(){

    int k=log2(n);

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

        for(int j=;j<=n;j++) dpmax[i][j][][]=dpmin[i][j][][]=val[i][j];

    for(int i=;i<=k;i++)//先求出一行内的最大值和最小值，然后再求出行间的最大值和最小值

        for(int j=;j<=k;j++){

            if(i== && j==) continue;

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

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

                    if(i==){//在同一行内

                        dpmax[r][c][i][j]=max(dpmax[r][c][i][j-],dpmax[r][c+(<<(j-))][i][j-]);

                        dpmin[r][c][i][j]=min(dpmin[r][c][i][j-],dpmin[r][c+(<<(j-))][i][j-]);

                    }

                    else {

                        dpmax[r][c][i][j]=max(dpmax[r][c][i-][j],dpmax[r+(<<(i-))][c][i-][j]);

                        dpmin[r][c][i][j]=min(dpmin[r][c][i-][j],dpmin[r+(<<(i-))][c][i-][j]);

                    }

        }

}

int query(int r,int c){

    int r1=r,c1=c,r2=r+b-,c2=c+b-,k=log2(b);

    int max1=dpmax[r1][c1][k][k];

    int max2=dpmax[r2-(<<k)+][c1][k][k];

    int max3=dpmax[r1][c2-(<<k)+][k][k];

    int max4=dpmax[r2-(<<k)+][c2-(<<k)+][k][k];

    int min1=dpmin[r1][c1][k][k];

    int min2=dpmin[r2-(<<k)+][c1][k][k];

    int min3=dpmin[r1][c2-(<<k)+][k][k];

    int min4=dpmin[r2-(<<k)+][c2-(<<k)+][k][k];

    return max(max(max1,max2),max(max3,max4))-min(min(min1,min2),min(min3,min4));

}

int main(){

    while(scanf("%d%d%d",&n,&b,&q)==){

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

            for(int j=;j<=n;j++) scanf("%d",&val[i][j]);

        ST();int r,c;

        while(q--){

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

            printf("%d\n",query(r,c));

        }

    }

    return ;

}

相关文章