題目大意：
給出一個(gè)N*N的矩陣，要查詢?nèi)我釨*B子矩陣內(nèi)的元素最大值和最小值之差。
思路：
這應(yīng)該算是一個(gè)二維的 RMQ 問題。但是做之前還不知道有RMQ這回事，就用一個(gè)動(dòng)態(tài)規(guī)劃做了。
還好速度也慢不到哪里去，也過了。哈哈。
#include <stdio.h>
struct node 
{
unsigned char arr[254], max, min;
};
__inline void node_init(struct node *n)
{
n->max = 0;
n->min = 255;
}
__inline void node_add(struct node *n, unsigned char val)
{
n->arr[val]++;
if (val > n->max)
n->max = val;
if (val < n->min)
n->min = val;
}
__inline void node_del(struct node *n, unsigned char val)
{
n->arr[val]--;
while (!n->arr[n->max])
n->max--;
while (!n->arr[n->min])
n->min++;
}
int N, B, K;
unsigned char data[256][256];
struct node row[256], col[256];
unsigned char ans[256][256];
int main()
{
int i, j, k;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d%d", &N, &B, &K);
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
scanf("%d", &k);
data[i][j] = k;
}
}
for (i = 0; i < N; i++) {
node_init(&row[i]);
for (j = 0; j < B; j++)
node_add(&row[i], data[i][j]);
}
for (i = 0; ; i++) {
node_init(&col[i]);
for (j = 0; j < B; j++) {
node_add(&col[i], row[j].max);
node_add(&col[i], row[j].min);
}
while (1) {
ans[j - B][i] = col[i].max - col[i].min;
if (j == N)
break;
node_del(&col[i], row[j - B].max);
node_del(&col[i], row[j - B].min);
node_add(&col[i], row[j].max);
node_add(&col[i], row[j].min);
j++;
}
if (i == N - B)
break;
for (j = 0; j < N; j++) {
node_del(&row[j], data[j][i]);
node_add(&row[j], data[j][i + B]);
}
}
while (K--) {
scanf("%d%d", &i, &j);
printf("%d\n", ans[i - 1][j - 1]);
}
return 0;
}