二维RMQ问题

前置知识

一维RMQ及其拓展

---

问题引入

• 题目地址IN

对于一个$n\times m$n×m的矩阵，每个格子有一个值，有$Q$Q个询问，每次询问你一个子矩阵中的最大值。

$1\leq n,m\leq 500,Q\leq 10^6$1≤n,m≤500,Q≤106

---

• 暴力

每次花子矩阵大小的复杂度去查询。
复杂度最坏$O(Q\times n\times m)$O(Q×n×m)

• 改进

我们用$n$n棵线段树或者树状数组来维护每行区间最大值，复杂度最坏$O(nmlogm+Qnlogm)$O(nmlogm+Qnlogm)，还是没法过，有没有更快的方法呢？

• 分析

既然是静态的询问，没有修改操作，那么很容易联想到$RMQ$RMQ中的$ST$ST表。

那么暴力的$ST$ST表就是和数据结构的做法类似，预处理$n$n个$ST$ST表，每次在多个$ST$ST表中查询最大值，复杂度最坏为$O(nmlogm+Qn)$O(nmlogm+Qn)，虽然能过更多的数据，但是还是不够。

• 二维$ST$ST表

既然查询对象是个二维矩阵，那么我们能不能维护一个二维的$ST$ST表呢？答案显然是肯定的。

预处理：

所以我们令$st[i][j][k][l]$st[i][j][k][l]，为新的$ST$ST表，表示以$(i,j)$(i,j)为左上角，右下角为$(i+2^k-1,j+2^l-1)$(i+2k−1,j+2l−1)的矩阵中的最大值，那么我们可以看出预处理的复杂度会是$O(nmlognlogm)$O(nmlognlogm)，所以对于询问数交少的还是用数据结构$O(nmlogm)$O(nmlogm)预处理查询比较好。

然后我们来看，对于每个$st[i][j][k][l]$st[i][j][k][l]，可以由哪些状态更新。

我们来看这个状态表示的矩阵，如下图：

假设这里左上角的点$A$A为$(i,j)$(i,j)，右下角点$D$D为$(i+2^k-1,j+2^l-1)$(i+2k−1,j+2l−1)，那么我们可以把它分成两部分，如下图：

那么我们将点$E$E看作$(i,j+2^{l-1})$(i,j+2l−1)，其实原来的大矩阵就可以由分成的这两个小矩阵更新得到，转移如下：
$st[i][j][k][l]=\max\{st[i][j][k][l-1],st[i][j+2^{l-1}][l-1]\}$st[i][j][k][l]=max{st[i][j][k][l−1],st[i][j+2l−1][l−1]}

其中，$\max$max里面第一个为上半部分矩阵，后面一个为下半部分矩阵。

如果$l=0$l=0的话，就将其竖起剖成两部分即可，是同理的。转移如下：

$st[i][j][k][l]=\max\{st[i][j][k-1][l],st[i+2^{k-1}][j][k-1][l]\}$st[i][j][k][l]=max{st[i][j][k−1][l],st[i+2k−1][j][k−1][l]}

所以最后按照$k,l$k,l从小到大更新即可。

查询

对于一个子矩阵，我们假设它的左上角坐标为$(x_1,y_1)$(x1​,y1​)，右下角为$(x_2,y_2)$(x2​,y2​)，那么可以通过预处理的二维$ST$ST表，将其分成四部分查询，如下图：

其中四个部分为图中$W_1(A,E,F,G),W_2(H,B,J,I),W_3(M,L,K,C),W_4(O,P,D,N)$W1​(A,E,F,G),W2​(H,B,J,I),W3​(M,L,K,C),W4​(O,P,D,N)，查询区间是可以重合的。

其实就对应了如下四个预处理的状态，我们令$p=log_2(x_2-x_1+1),q=log_2(y_2-y_1+1)$p=log2​(x2​−x1​+1),q=log2​(y2​−y1​+1)：

$\max\begin{cases}st[x_1][y_1][p][q]\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \rightarrow\ \ W_1\\ st[x_2-2^p+1][y_1][p][q] \ \ \ \ \ \ \ \ \ \ \rightarrow\ \ W_2\\ st[x_1][y_2-2^q+1][p][q]\ \ \ \ \ \ \ \ \ \ \rightarrow\ \ W_3\\ st[x_2-2^p+1][y_2-2^q+1] \ \ \ \rightarrow\ \ W_4\end{cases}\bigg\}\rightarrow ans$max⎩⎪⎪⎪⎨⎪⎪⎪⎧​st[x1​][y1​][p][q]                         →  W1​st[x2​−2p+1][y1​][p][q]          →  W2​st[x1​][y2​−2q+1][p][q]          →  W3​st[x2​−2p+1][y2​−2q+1]   →  W4​​}→ans

答案就为上面四个矩阵的$\max$max，所以预处理对数，每次$O(1)$O(1)回答即可。

---

那么总的复杂度为$O(nmlognlogm+Q)$O(nmlognlogm+Q)，是可以过的了。

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int Log=12;
const int N=610;
const int inf=1e9;
int n,m,Q;
int maxv[Log][Log][N][N];
int pre[N],val[N][N]; 
void init(){
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)maxv[0][0][i][j]=val[i][j];
	pre[2]=pre[3]=1;
	for(int i=4,up=max(n,m);i<=up;i++)pre[i]=pre[i>>1]+1;
	int up1=pre[n]+1,up2=pre[m]+1;
	for(int l1=0;l1<=up1;l1++){
		for(int l2=0;l2<=up2;l2++){
			if(!l1&&!l2) continue;
			for(int i=1;(i+(1<<l1)-1)<=n;i++){
				for(int j=1;(j+(1<<l2)-1)<=m;j++){
					if(l2)maxv[l1][l2][i][j]=max(maxv[l1][l2-1][i][j],maxv[l1][l2-1][i][j+(1<<(l2-1))]);
					else maxv[l1][l2][i][j]=max(maxv[l1-1][l2][i][j],maxv[l1-1][l2][i+(1<<(l1-1))][j]);
				}
			}
		}
	}
}
int query(int x1,int y1,int x2,int y2){
	int p=pre[x2-x1+1],q=pre[y2-y1+1];
	int ans=-inf;
	ans=max(maxv[p][q][x1][y1],maxv[p][q][x1][y2-(1<<q)+1]);
	ans=max(ans,max(maxv[p][q][x2-(1<<p)+1][y1],maxv[p][q][x2-(1<<p)+1][y2-(1<<q)+1]));
	return ans;
}
int x1,x2,y1,y2;
int main(){
	scanf("%d%d%d",&n,&m,&Q);
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&val[i][j]);
	init();
	for(int i=1;i<=Q;i++){
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		printf("%d\n",query(x1,y1,x2,y2));
	}
	return 0;
}