矩阵最值

题目描述

我们有一个N  行  M列的矩阵，现在小Q有 K 个问题，每次询问一个以 (X₁,Y₁)为左上角， (X₂,Y₂)为右下角的子矩阵的最大值。

输入格式

第一行三个整数 N,M,K 。

接下来 N 行，每行有  M个整数，设A_i,j  为矩阵 i 行j  列的数字。

接下来 k 行，每行 4 个整数  X₁,Y₁,X₂,Y₂。

输出格式

共 k 行，每行对应一个答案。

样例

样例输入

3 4 5
789 15225 27847 6452 
3976 18268 23626 1943 
13336 26216 17321 4960 
2 2 3 4
2 3 3 4
2 1 3 4
1 3 2 4
1 2 3 2

样例输出

26216
23626
26216
27847
26216

数据范围

对于  的数据，1<=N,M<=250,1<=K<=1E6，1<=X1<=X2<=N，1<=Y1<=Y2<=M。

 求左上角为（1，1）右下角为（11，11）区域的最大值F(1,1,11,11)，可以从图中4个小区域的最大值求最大得到

F(1,1,11,11)=max{F(1,1,8,8),F(1,3,8,11),F(3,1,8,8),F(3,3,11,11)}

1）我们改用倍增思想，预处理所有长宽是2的若干次幂的矩形区域的最大值：

设F[i,j,k,h]表示左上角为（i，j）长度为2^k  高度为2^h，的矩形区域的最大值。

F[i,j,k,h]=max{ F[i,j,k-1,h],F[i+2^k-1,j,k-1,h],F[i,j,k,h-1],F[i,j+2^h-1,k,h-1]  }

2）询问一个以 (X₁,Y₁)为左上角， (X₂,Y₂)为右下角的子矩阵的最大值时，

k=log[x2-x1+1]

h=log[y2-y1+1]

ans=max{f[x1,y1,k,h],f[x2-2^k+1,y1,k,h],f[x1,y2-2^h+1,k,h],f[x2-2^k+1,y2-2^h+1,k,h]}

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 
 5 // 快读 
 6 int read(){
 7     int x = 0, f = 1;char c = getchar();
 8     while(c < '0' || c > '9'){if(c == '-'){f = -1;}c = getchar();}
 9     while(c >= '0' && c <= '9'){x = x*10+c-'0';c = getchar();}
10     return x*f;
11 }
12 //快写
13 inline void write(int x){
14     if(x<0) { putchar('-'); x = -x;}
15     if(x>9) write(x / 10);
16     putchar(x % 10 + '0');
17 }
18 
19 
20 const int N = 255;
21 const int M = 255;
22 int dp[N][M][20][20],logn[N];
23 
24 int n,m,q;
25 void rmq_init() //关键是递推的顺序 
26 {
27     
28     for(int k=0;k<=logn[n];k++)
29         for(int h=0;h<=logn[m];h++){
30             if(!k&&!h) continue;        
31             for(int i=1;i+(1<<k)-1<=n;i++)
32             for(int j=1;j+(1<<h)-1<=m;j++)
33                     if(k)
34                         dp[i][j][k][h]=max(dp[i][j][k-1][h],dp[i+(1<<(k-1))][j][k-1][h]);
35                     else
36                         dp[i][j][k][h]=max(dp[i][j][k][h-1],dp[i][j+(1<<(h-1))][k][h-1]);
37            }    
38 }
39 
40 int rmq_q(int x1,int y1,int x2,int y2)
41 {
42     int k=logn[x2-x1+1],h=logn[y2-y1+1];
43     int max1=max(dp[x1][y1][k][h],dp[x2-(1<<k)+1][y1][k][h]);
44     int max2=max(dp[x1][y2-(1<<h)+1][k][h],dp[x2-(1<<k)+1][y2-(1<<h)+1][k][h]);
45     return max(max1,max2);
46 }
47 
48 int main(){
49     n=read();m=read();q=read();//输入数据总数
50     
51     logn[0]=-1;
52     for(int i=1;i<=max(n,m);i++) 
53         logn[i]=logn[i/2]+1;
54     
55     for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) dp[i][j][0][0]=read();
56     
57     rmq_init();//预处理
58     
59     //cin>>m;//输入询问次数q
60     for(int i=1;i<=q;i++)
61         {   
62             int x1=read(),y1=read(),x2=read(),y2=read(); 
63             int ans=rmq_q(x1,y1,x2,y2);
64             write(ans);putchar('\n');
65             
66         }
67         
68     return 0;
69 }