ST表 O(abn)做法 TLE50pts求助

#include <bits/stdc++.h>
using namespace std;
#define M 1005
#define N 105
const int inf=1e9+7;
int n,m,k,a[M][M],f[M][M][15][2],ans=inf,t2[N];
void Sol(int z)//ST表,复杂度O(m)带10的常数,加上外面那一层预处理应该是O(10nm)
{
	for(int i=1;i<=m;i++) f[z][i][0][0]=f[z][i][0][1]=a[z][i];
	for(int j=1;j<=10;j++)
	{
		if(t2[j]>m) break;
		for(int i=1;i<=m;i++)
		{
			f[z][i][j][0]=max(f[z][i][j-1][0],f[z][i+t2[j-1]][j-1][0]);
			f[z][i][j][1]=min(f[z][i][j-1][1],f[z][i+t2[j-1]][j-1][1]);
		}
	}
}
int Get(int z,int l,int r,int tk)//获取a[z][l]到a[z][r]这一段的最大值/最小值
{
	int J=log2((r-l+1));
	return (tk==0?max(f[z][l][J][tk],f[z][r-t2[J]+1][J][tk]):min(f[z][l][J][tk],f[z][r-t2[J]+1][J][tk]));//0=max,1=min
}
int Don(int x,int y)//合并每一行的最大值/最小值,求差,复杂度O(k),加上外面的O(nm)求解复杂度应该是O(nmk),1e8
{
	int xn=0,in=inf;
	for(int i=x;i<=x+k-1;i++)
	{
		xn=max(xn,Get(i,y,y+k-1,0)),in=min(in,Get(i,y,y+k-1,1));
	}
	return xn-in;
}
int main()
{
	cin>>n>>m>>k,t2[0]=1; for(int i=1;i<=15;i++) t2[i]=t2[i-1]*2;//预处理Pow(2,i)
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j];
	for(int i=1;i<=n;i++) Sol(i);//预处理每一行
	for(int i=1;i<=n-k+1;i++) for(int j=1;j<=m-k+1;j++) ans=min(ans,Don(i,j));//枚举正方形
	cout<<ans<<endl;
	return 0;
}