poj2019 二维RMQ模板题

和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 ;
}
上一篇:ZOJ 2859 二维线段树


下一篇:text/plain && text/html