第四题：跳跃
背景：
事情出奇的顺利，自从高考研讨会过后，z 同学专心准备 noip2010 。可能是被 z 同学的 潇洒、帅气、阳关所吸引，zn 主动约到了 z 同学，就这样，zn 与 z 同学走到了一起~！那是 一次放假，众所周知，hz 的放假，对于不回家的同学就是能走出封闭的 hz 大门好好玩上3 个小时。Zn 刚与 z 同学吃完 kfc，他们来到了衡水唯一还算比较浪漫的地方(貌似叫什么人 民公园吧，ms 了~~）。
题目描述：
公园中有许多木桩，每个木桩都有一个高度，活泼的小 z 同学喜欢从一个木桩跳到另 一个木桩上，zn 说太危险了，于是 z 同学让 zn 算出每一次跳跃的危险系数。小 z 每一次跳 跃的范围是一个 k*k 的矩形，危险系数为这个矩形内最高的木桩高度减去最小的。身为 oier， 你能比学数奥的 zn 算的快吗
输入：
第一行三个整数 n(木桩为 n*n 的矩阵）、k、b（小 zz 准备跳跃的次数） 接下来为 n*n 的矩阵，描述木桩的高度
接下来 b 行；每行两个整数 x,y(表示 z 同学跳跃的范围的左上角为第 x 行第 y 列）， 保证跳跃范围不超过矩阵的范围
输入：
B 行，每行对应一次跳跃的危险系数样例输入：
5 3 1
5 1 2 6 3<<------------------第一行
1 3 5 2 7
7 2 4 6 1
9 9 8 6 5
0 6 9 3 9
1 2
样例输出：
5
数据范围：
对于30%的数据
0<k<=n<=2500<b<=100
对于100%的数据
0<k<-n<=2500<b<=1000 000
二维的 RMQ ，解法有好多种：
带标号快排，然后从两端开始找，找到编号满足条件的跳出。（这个东西均摊复杂度很低，但极端情况复杂度巨高，适合对付随机数据，相当好打） 90 。
代码 （SueMiller）
program ACRush;
var a:array[0..90000,1..3]of longint;
i,j,x,y,l,r:longint;
n,k,b,temp:longint;
procedure quicksort(l,r:longint);
var x,i,j:longint;
begin
i:=l; j:=r; x:=a[(l+r)>>1,1];
repeat
while a[i,1]<x do inc(i);
while x<a[j,1] do dec(j);
if i<=j then
begin
a[0]:=a[i]; a[i]:=a[j]; a[j]:=a[0];
inc(i); dec(j);
end;
until i>j;
if l<j then quicksort(l,j);
if i<r then quicksort(i,r);
end;
begin
assign(input,'jump.in');reset(input);
assign(output,'jump.out');rewrite(output);
readln(n,k,b);
fillchar(a,sizeof(a),0);
temp:=0;
for i:=1 to n do
begin
for j:=1 to n do
begin
read(x);
inc(temp);
a[temp,1]:=x;
a[temp,2]:=i;
a[temp,3]:=j;
end;
readln;
end;
quicksort(1,temp);
for i:=1 to b do
begin
readln(x,y);
for l:=1 to temp do
if ((a[l,2]>=x) and (a[l,2]<=x+k-1))
and ((a[l,3]>=y) and (a[l,3]<=y+k-1))
then break;
for r:=temp downto 1 do
if ((a[r,2]>=x) and (a[r,2]<=x+k-1))
and((a[r,3]>=y) and (a[r,3]<=y+k-1))
then break;
writeln(a[r,1]-a[l,1]);
end;
close(input);close(output);
End.
观察它的数据，会发现询问很多，矩阵很小，所以，可以先把矩阵拆成一行一行的，然后求出每一行中，每一段的最值，用单调队列或 ST ，然后，当读入数据时，将需要求得矩阵的每一行的最值加以比较，比较难打。 100 。
代码（LYF）
var
a,max,min,l,r:array[0..255,0..255] of longint;
q:array[0..255] of longint;
x,y,head,tail,i,j,k,n,m,qq:longint;
begin
assign(input,'jump.in'); reset(input);
assign(output,'jump.out'); rewrite(output);
readln(n,m,qq);
for i:=1 to n do
for j:=1 to n do
read(a[i,j]);
for i:=1 to n do
begin
head:=1; tail:=1; q[1]:=1;
for j:=1 to m-1 do
begin
while (head<=tail)and(a[i,q[tail]]>=a[i,j]) do dec(tail);
inc(tail);
q[tail]:=j;
end;
for j:=m to n do
begin
while (head<=tail)and(q[head]+m-1<j) do inc(head);
while (head<=tail)and(a[i,q[tail]]>=a[i,j]) do dec(tail);
inc(tail);
q[tail]:=j;
l[i,j]:=a[i,q[head]];
end;
end;
for i:=1 to n do
begin
head:=1; tail:=1; q[1]:=1;
for j:=1 to m-1 do
begin
while (head<=tail)and(a[i,q[tail]]<=a[i,j]) do dec(tail);
inc(tail);
q[tail]:=j;
end;
for j:=m to n do
begin
while (head<=tail)and(q[head]+m-1<j) do inc(head);
while (head<=tail)and(a[i,q[tail]]<=a[i,j]) do dec(tail);
inc(tail);
q[tail]:=j;
r[i,j]:=a[i,q[head]];
end;
end;
for j:=m to n do
begin
head:=1; tail:=1; q[1]:=1;
for i:=1 to m-1 do
begin
while (head<=tail)and(l[q[tail],j]>=l[i,j]) do dec(tail);
inc(tail);
q[tail]:=i;
end;
for i:=m to n do
begin
while (head<=tail)and(q[head]+m-1<i) do inc(head);
while (head<=tail)and(l[q[tail],j]>=l[i,j]) do dec(tail);
inc(tail);
q[tail]:=i;
min[i,j]:=l[q[head],j];
end;
end;
for j:=m to n do
begin
head:=1; tail:=1; q[1]:=1;
for i:=1 to m-1 do
begin
while (head<=tail)and(r[q[tail],j]<=r[i,j]) do dec(tail);
inc(tail);
q[tail]:=i;
end;
for i:=m to n do
begin
while (head<=tail)and(q[head]+m-1<i) do inc(head);
while (head<=tail)and(r[q[tail],j]<=r[i,j]) do dec(tail);
inc(tail);
q[tail]:=i;
max[i,j]:=r[q[head],j];
end;
end;
for i:=1 to qq do
begin
readln(x,y);
x:=x+m-1;
y:=y+m-1;
writeln(max[x,y]-min[x,y]);
end;
close(input); close(output);
end.
二维 ST ，首先，将一个大矩阵分成 2^k*2^k 的小矩阵，求出小矩阵中的最值，然后每读入一个矩阵后将它分解成小矩阵，直接比较求最值，还算好打，但不好想。 100 。
代码（ZSZ）
program foreverzsz;
var f,g:array[0..250,0..250,0..15] of longint;
n,b,k,i,j,ii,jj,w,i1,j1,minn,maxx,kk:longint;
d:array[0..15] of longint;
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
begin
assign(input,'jump.in');reset(input);
assign(output,'jump.out');rewrite(output);
readln(n,b,kk);
fillchar(f,sizeof(f),120);
fillchar(g,sizeof(g),0);
for i:= 1 to n do
for j:= 1 to n do
begin
read(f[i][j][0]);
g[i][j][0]:=f[i][j][0];
end;
d[0]:=1;
for k:= 1 to 12 do
d[k]:=d[k-1]<<1;
w:=trunc(ln(b)/ln(2));
for k:= 1 to w do
for i:= 1 to n do
for j:= 1 to n do
if (i+d[k]-1<=n)and(j+d[k]-1<=n) then
begin
f[i][j][k]:=min(f[i][j][k-1],f[i+d[k-1]][j][k-1]);
f[i][j][k]:=min(f[i][j][k],f[i][j+d[k-1]][k-1]);
f[i][j][k]:=min(f[i][j][k],f[i+d[k-1]][j+d[k-1]][k-1]);
g[i][j][k]:=max(g[i][j][k-1],g[i+d[k-1]][j][k-1]);
g[i][j][k]:=max(g[i][j][k],g[i][j+d[k-1]][k-1]);
g[i][j][k]:=max(g[i][j][k],g[i+d[k-1]][j+d[k-1]][k-1]);
end;
for i:= 1 to kk do
begin
readln(ii,jj);
i1:=ii+b-1;
j1:=jj+b-1;
if f[ii][jj][w]<f[i1-d[w]+1][j1-d[w]+1][w] then minn:=f[ii][jj][w] else minn:=f[i1-d[w]+1][j1-d[w]+1][w];
if f[ii][j1-d[w]+1][w]<minn then minn:=f[ii][j1-d[w]+1][w];
if f[i1-d[w]+1][jj][w]<minn then minn:=f[i1-d[w]+1][jj][w];
if g[ii][jj][w]>g[i1-d[w]+1][j1-d[w]+1][w] then maxx:=g[ii][jj][w] else maxx:=g[i1-d[w]+1][j1-d[w]+1][w];
if g[ii][j1-d[w]+1][w]>maxx then maxx:=g[ii][j1-d[w]+1][w];
if g[i1-d[w]+1][jj][w]>maxx then maxx:=g[i1-d[w]+1][jj][w];
writeln(maxx-minn);
end;
close(input);
close(output);
end.
这三个方法都可以用在更高维的地方，当然，第二个要是用在高维（四维以上），前提条件是你得有着十分强悍的高维空间想象力。