二维RMQ
# include <stdio.h>
# define N 255
# define L 8
int n, b, k, ll, jj;
int h[N][N];
int mx[N][N][L], mn[N][N][L];
int Max(int x, int y)
{
return x > y ? x : y;
}
int Min(int x, int y)
{
return x < y ? x : y;
}
void init(void)
{
int i, j;
scanf("%d%d%d", &n, &b, &k);
for (i = 1; i <= n; ++i)
for (j = 1; j <= n; ++j)
{
scanf("%d", &h[i][j]);
mx[i][j][0] = mn[i][j][0] = h[i][j];
}
}
void prep(void)
{
int p, q, j, l;
jj = 0, ll = 1;
while (ll*2 <= b) ++jj, ll *= 2;
for (j = 1, l = 1; l <= ll; l *= 2, ++j)
for (p = 1; p+l*2 <= n+1; ++p)
for (q = 1; q+l*2 <= n+1; ++q)
{
mx[p][q][j] = Max(Max(mx[p][q][j-1], mx[p+l][q+l][j-1]),
Max(mx[p][q+l][j-1], mx[p+l][q][j-1]));
mn[p][q][j] = Min(Min(mn[p][q][j-1], mn[p+l][q+l][j-1]),
Min(mn[p][q+l][j-1], mn[p+l][q][j-1]));
//printf("%d %d\t%d %d\t%d\n", p, q, mx[p][q][j], mn[p][q][j], l);
}
}
int rmq(int x, int y)
{
/**//*
int s, t;
s = Max(Max(mx[x][y][jj], mx[x+b-ll][y+b-ll][jj]),
Max(mx[x+b-ll][y][jj], mx[x][y+b-ll][jj]));
t = Min(Min(mn[x][y][jj], mn[x+b-ll][y+b-ll][jj]),
Min(mn[x+b-ll][y][jj], mn[x][y+b-ll][jj]));
printf("%d\t%d\n", s, t);
*/
return Max(Max(mx[x][y][jj], mx[x+b-ll][y+b-ll][jj]),
Max(mx[x+b-ll][y][jj], mx[x][y+b-ll][jj])) -
Min(Min(mn[x][y][jj], mn[x+b-ll][y+b-ll][jj]),
Min(mn[x+b-ll][y][jj], mn[x][y+b-ll][jj]));
}
void solve(void)
{
int i, x, y;
for (i = 1; i <= k; ++i)
{
scanf("%d%d", &x, &y);
printf("%d\n", rmq(x, y));
}
}
int main()
{
// freopen("test.in", "r", stdin);
init();
prep();
solve();
return 0;
}
posted on 2012-08-27 09:00
yajunw 阅读(110)
评论(0) 编辑 收藏 引用