二维ST表模板

矩阵查询最大值，相当于查询的时候一个矩形拆成(4)个小矩形，和一维(ST)表相差无几

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f,N = 255;
inline ll read()
{
	ll ret=0;char ch=' ',c=getchar();
	while(!(c>='0'&&c<='9')) ch=c,c=getchar();
	while(c>='0'&&c<='9') ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
	return ch=='-'?-ret:ret;
}
int st[N][N][21][21],n,m,Q,logn[N];
void buildst()
{
	int k=0;
	for(int i=1;i<=max(n,m);i++)
	{
		if(1<<k<=i) k++;
		logn[i]=k-1;
	}
	for(int k=0;1<<k<=n;k++)
		for(int p=0;1<<p<=m;p++)
			for(int i=1;i+(1<<k)-1<=n;i++)	
				for(int j=1;j+(1<<p)-1<=m;j++)
				{
					if(!k&&!p) continue;
					if(k) st[i][j][k][p]=max(st[i][j][k-1][p],st[i+(1<<(k-1))][j][k-1][p]);
					if(p) st[i][j][k][p]=max(st[i][j][k][p-1],st[i][j+(1<<(p-1))][k][p-1]);
				}
	
}
inline int Max(int a,int b,int c,int d){return max(max(a,b),max(c,d));}
inline int query(int xa,int ya,int xb,int yb)
{
	int k1=logn[xb-xa+1],k2=logn[yb-ya+1];
	return Max(st[xa][ya][k1][k2],st[xa][yb-(1<<k2)+1][k1][k2],
			   st[xb-(1<<k1)+1][ya][k1][k2],st[xb-(1<<k1)+1][yb-(1<<k2)+1][k1][k2]); 
}
int main()
{
	n=read(),m=read();	Q=read();
	for(int i=1;i<=n;i++) 
		for(int j=1;j<=m;j++) st[i][j][0][0]=read();

	buildst();
	while(Q--)
	{
		int xa=read(),ya=read(),xb=read(),yb=read();
		printf("%d
",query(xa,ya,xb,yb)); 
	}
	return 0;
}