子矩阵_(单调队列)

原题链接：4964. 子矩阵 - AcWing题库

题意：给定矩阵与子矩阵大小，要求每个子矩阵最大值与最小值，最后输出各个子矩阵最大值最小值乘积的和取模

思路

范围1000，$nm$就是$1000000$ ，要将时间复杂度限制在 $nm$ 或 $nmlogn$ 级别

在限制长度的区间内找最大最小值，明显的单调队列 但是二维

想办法化为一维

• 先对每行找最大或最小，把找到的值记在矩阵中
• 再对矩阵做每列的最大最小值

转化为两个一维

实现

#include <iostream>
#include <algorithm>
#include <cstring>
 
using namespace std;
 
typedef long long LL;
 
const int N = 1010, mod = 998244353;
 
LL A[N][N];
LL c[N][N], d[N][N];
LL ans_min[N][N], ans_max[N][N];
int q[N];
 
int n, m, a, b;
 
int main()
{
    cin >> n >> m >> a >> b;
    
    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 ++)
    {
        int hh = 1, tt = 0;
        //找最小值
        for(int j = 1; j <= m; j ++)
        {
            //长度超了
            if(hh <= tt && j - b + 1 > q[hh]) hh ++;
            while(hh <= tt && A[i][q[tt]] >= A[i][j]) tt --;
            
            q[++ tt] = j;
            
            if(j - b + 1 >= 0) c[i][j] = A[i][q[hh]];
        }
        
        hh = 1, tt = 0;
        //找最大值
        for(int j = 1; j <= m; j ++)
        {
            if(hh <= tt && j - b + 1 > q[hh]) hh ++;
            while(hh <= tt && A[i][q[tt]] <= A[i][j]) tt --;
            
            q[++ tt] = j;
            
            if(j - b + 1 >= 0) d[i][j] = A[i][q[hh]];
        }
    }
    
    //用行找全局最大最小
    for(int j = b; j <= m; j ++)
    {
        int hh = 1, tt = 0;
        for(int i = 1; i <= n; i ++)
        {
            if(hh <= tt && i - a + 1 > q[hh]) hh ++;
            while(hh <= tt && c[q[tt]][j] >= c[i][j]) tt --;
            
            q[++ tt] = i;
            
            if(i - a + 1 >= 0) ans_min[i][j] = c[q[hh]][j];
            
        }
        
        hh = 1, tt = 0;
        for(int i = 1; i <= n; i ++)
        {
            if(hh <= tt && i - a + 1 > q[hh]) hh ++;
            while(hh <= tt && d[q[tt]][j] <= d[i][j]) tt --;
            
            q[++ tt] = i;
            
            if(i - a + 1 >= 0) ans_max[i][j] = d[q[hh]][j];
            
        }
    }
    
    LL ans = 0;
    for(int i = a; i <= n; i ++)
        for(int j = b; j <= m; j ++)
        {
            ans += (ans_max[i][j] % mod) * (ans_min[i][j] % mod) % mod;
            ans = ans % mod;
        }
        
    cout << ans << endl;
    
    return 0;
}

实际上空间用得有点多，可以尝试开一维的空间来存储