题意

求一个区间最大差值

思路

很复杂,但是思路比较简单

二维的ST表

其实就是四个角的 max,min

代码

原本的代码不长(只有44行),这是展开的

#include<iostream>
#include<algorithm>
/*
这个头文件可以让 max,min 同时比较多项
语法:
max({xxx,xxx,xxx,...})
min({xxx,xxx,xxx,...})
*/
#define N 300
using namespace std;
int n,l,t;
int stma[N][N][32];
int stmi[N][N][32];
int lg[N];
int len(int x,int y,int a,int b)//求一个区间最大差值
{
	int k=lg[a-x+1];
	int ma=max
	({
		stma[x][y][k],//左上角
		stma[a-(1<<k)+1][y][k],//左下角
		stma[x][b-(1<<k)+1][k],//右上角
		stma[a-(1<<k)+1][b-(1<<k)+1][k]//右下角
	});//这4项需要仔细推一下
	int mi=min
	({
		stmi[x][y][k],
		stmi[a-(1<<k)+1][y][k],
		stmi[x][b-(1<<k)+1][k],
		stmi[a-(1<<k)+1][b-(1<<k)+1][k]
	});//以次类推
	return ma-mi;
}
int main()
{
	cin>>n>>l>>t;
	lg[1]=0;
	for(int i=2;i<=n;i++)
		lg[i]=lg[i>>1]+1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		{
			cin>>stma[i][j][0];
			stmi[i][j][0]=stma[i][j][0];
		}
	for(int k=1;k<=lg[n];k++)
		for(int i=1;i<=n-(1<<k)+1;i++)
			for(int j=1;j<=n-(1<<k)+1;j++)
				stma[i][j][k]=max
				({
					stma[i][j][k-1],//左上角
					stma[i+(1<<(k-1))][j][k-1],//左下角
					stma[i][j+(1<<(k-1))][k-1],//右上角
					stma[i+(1<<(k-1))][j+(1<<(k-1))][k-1]//右下角
				});//这4项需要仔细推一下
	for(int k=1;k<=lg[n];k++)
		for(int i=1;i<=n-(1<<k)+1;i++)
			for(int j=1;j<=n-(1<<k)+1;j++)
				stmi[i][j][k]=min
				({
					stmi[i][j][k-1],
					stmi[i+(1<<(k-1))][j][k-1],
					stmi[i][j+(1<<(k-1))][k-1],
					stmi[i+(1<<(k-1))][j+(1<<(k-1))][k-1]
				});//以次类推
	while(t--)
	{
		int x,y;
		cin>>x>>y;
		cout<<len(x,y,x+l-1,y+l-1)<<"\n";//虽然已经给了b的值,但是这样写是万能的
	}
	return 0;
}

附

44行的代码(我提交上去的代码)

密密麻麻

#include<iostream>
#include<algorithm>
#define N 300
using namespace std;
int n,l,t;
int stma[N][N][32];
int stmi[N][N][32];
int lg[N];
int len(int x,int y,int a,int b)
{
	int k=lg[a-x+1];
	int ma=max({stma[x][y][k],stma[a-(1<<k)+1][y][k],stma[x][b-(1<<k)+1][k],stma[a-(1<<k)+1][b-(1<<k)+1][k]});
	int mi=min({stmi[x][y][k],stmi[a-(1<<k)+1][y][k],stmi[x][b-(1<<k)+1][k],stmi[a-(1<<k)+1][b-(1<<k)+1][k]});
	return ma-mi;
}
int main()
{
	cin>>n>>l>>t;
	lg[1]=0;
	for(int i=2;i<=n;i++)
		lg[i]=lg[i>>1]+1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		{
			cin>>stma[i][j][0];
			stmi[i][j][0]=stma[i][j][0];
		}
	for(int k=1;k<=lg[n];k++)
		for(int i=1;i<=n-(1<<k)+1;i++)
			for(int j=1;j<=n-(1<<k)+1;j++)
				stma[i][j][k]=max({stma[i][j][k-1],stma[i+(1<<(k-1))][j][k-1],stma[i][j+(1<<(k-1))][k-1],stma[i+(1<<(k-1))][j+(1<<(k-1))][k-1]});
	for(int k=1;k<=lg[n];k++)
		for(int i=1;i<=n-(1<<k)+1;i++)
			for(int j=1;j<=n-(1<<k)+1;j++)
				stmi[i][j][k]=min({stmi[i][j][k-1],stmi[i+(1<<(k-1))][j][k-1],stmi[i][j+(1<<(k-1))][k-1],stmi[i+(1<<(k-1))][j+(1<<(k-1))][k-1]});
	while(t--)
	{
		int x,y;
		cin>>x>>y;
		cout<<len(x,y,x+l-1,y+l-1)<<"\n";
	}
	return 0;
}

题意

求二维区间的最大值减最小值，也就是 #P2880. [USACO07JAN] Balanced Lineup G 二维版。

思路

一看就想到 ST 表^[1]，但如何基于二维数组做 ST 表呢？

假设目标为取最大值。

普通 ST 表是将原数组变成二维，然后对于第 $j$ 列，把 $[i,i+2^j-1]$ 间的最大值存起来。

那对于二维数组，ST 表应该是三维，但这个标准怎么取呢？

我们从三维角度看，首先我们要从上一层拿几个区间取最大值。由于要存二维区块的最大值，那我们就拿上一层四个区块。当 $a_{i,j,k}$ 存的是以 $i_1,j_1,k-1$ 为左上角的边长为 $4$（跟一维 ST 表一样，取 $2$ 的次方）的区块时，我们取的四个区块如下图：

x...x...
........
........
........
x...x...
........
........
........

稍微更改一维 ST 表的代码便能做出二维 ST 表。

查询就是查询四个区块的最大值。

由于题目要求最大与最小的差，所以再复制个最小值的 ST 表就行了。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 250,LOG2N = 10;
int mx[N][N][LOG2N],mn[N][N][LOG2N],Log2[N]; 
int main(int argc, char **argv){
	int n,b,k;
	cin >> n >> b >> k;
	for (int i = 1;i <= n;i++){
		for (int j = 1;j <= n;j++){
			cin >> mx[i][j][0];
			mn[i][j][0] = mx[i][j][0];
		}
	}
	for (int i = 2;i <= n;i++){
		Log2[i] = Log2[i >> 1] + 1;
	}
	for (int h = 1;h <= Log2[n];h++){
		for (int i = 1;i <= n - (1 << h) + 1;i++){
			for (int j = 1;j <= n - (1 << h) + 1;j++){
				mx[i][j][h] = max({mx[i][j][h - 1],mx[i + (1 << (h - 1))][j][h - 1],mx[i][j + (1 << (h - 1))][h - 1],mx[i + (1 << (h - 1))][j + (1 << (h - 1))][h - 1]});
				mn[i][j][h] = min({mn[i][j][h - 1],mn[i + (1 << (h - 1))][j][h - 1],mn[i][j + (1 << (h - 1))][h - 1],mn[i + (1 << (h - 1))][j + (1 << (h - 1))][h - 1]});
			}
		}
	}
	while (k--){
		int r,c;
		cin >> r >> c;
		int p = Log2[b];
		printf("%d\n",max({mx[r][c][p],mx[r + b - (1 << p)][c][p],mx[r][c + b - (1 << p)][p],mx[r + b - (1 << p)][c + b - (1 << p)][p]}) - min({mn[r][c][p],mn[r + b - (1 << p)][c][p],mn[r][c + b - (1 << p)][p],mn[r + b - (1 << p)][c + b - (1 << p)][p]}));
	}
	return 0;
}

请自己思考尝试后再看题解。

推荐题解：

https://www.cnblogs.com/Aya-Uchida/p/11332822.html

然后还有一篇相关题目的题解，是另一个解法，推荐阅读：

https://www.cnblogs.com/Aya-Uchida/p/11332856.html