单调队列优化

1. 子矩阵

来源：第十四届蓝桥杯省赛C++C组
题目链接

题目描述

给定一个 $n × m$ （$n$ 行 $m$ 列）的矩阵。

设一个矩阵的价值为其所有数中的最大值和最小值的乘积。

求给定矩阵的所有大小为 $a × b$ （$a$ 行 $b$ 列）的子矩阵的价值的和。

答案可能很大，你只需要输出答案对 $998244353$ 取模后的结果。

输入格式

输入的第一行包含四个整数分别表示 $n, m, a, b$，相邻整数之间使用一个空格分隔。

接下来 $n$ 行每行包含 $m$ 个整数，相邻整数之间使用一个空格分隔，表示矩阵中的每个数 $A_{i,j}$。

输出格式

输出一行包含一个整数表示答案。

数据范围

对于 $40\%$ 的评测用例，$1 ≤ n, m ≤ 100$；
对于 $70\%$ 的评测用例，$1 ≤ n, m ≤ 500$；
对于所有评测用例，$1 ≤ a ≤ n ≤ 1000$，$1 ≤ b ≤ m ≤ 1000$，$1 ≤ A_{i,j} ≤ 10^9$。

输入样例：

2 3 1 2
1 2 3
4 5 6

输出样例：

58

样例解释

$1 × 2 + 2 × 3 + 4 × 5 + 5 × 6 = 58$。

算法：（单调队列）\(O(nm)\)

算法内容

• 我们用单调队列优化求解二维矩阵的最大值和最小值的过程。

• 首先用\(rmin\)和\(rmax\)数组预处理原数组中每一行的长度为\(b\)的滑动窗口的最小值和最大值，预处理完成后，\(rmin(i, j)\)即\(rmin\)数组的第\(i\)行第\(j\)列的元素的值就是原数组的第\(i\)行中前\(j\)个元素中的最小值；然后我们用\(resmin\)和\(resmax\)数组预处理\(rmin\)和\(rmax\)数组中的每一列的长度为\(a\)的最小值和最大值，注意此时我们要把\(rmin\)和\(rmax\)数组中的每一列的元素拿出来放到一个临时数组里才能传入函数。

• 行列都预处理完成后，每一个子矩阵的右下角的\(rmin\)和\(rmax\)的值就是整个子矩阵的最小值和最大值。

C++代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1010, mod = 998244353;

int n, m, a, b;
int w[N][N];
int q[N];
int rmin[N][N], rmax[N][N];

void get_min(int arr[], int res[], int tot, int k)
{
    int hh = 0, tt = -1;
    for (int i = 1; i <= tot; i ++ )
    {
        if (hh <= tt && q[hh] < i - k + 1) hh ++ ;
        while (hh <= tt && arr[q[tt]] >= arr[i]) tt -- ;
        q[++ tt] = i;
        res[i] = arr[q[hh]];
    }
}

void get_max(int arr[], int res[], int tot, int k)
{
    int hh = 0, tt = -1;
    for (int i = 1; i <= tot; i ++ )
    {
        if (hh <= tt && q[hh] < i - k + 1) hh ++ ;
        while (hh <= tt && arr[q[tt]] <= arr[i]) tt -- ;
        q[++ tt] = i;
        res[i] = arr[q[hh]];
    }
}

int main()
{
    cin >> n >> m >> a >> b;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            scanf("%d", &w[i][j]);
    
    for (int i = 1; i <= n; i ++ )
    {
        get_min(w[i], rmin[i], m, b);
        get_max(w[i], rmax[i], m, b);
    }
    
    LL ans = 0;
    
    int arr[N], resmin[N], resmax[N];
    for (int col = b; col <= m; col ++ ) //枚举列
    {
        for (int i = 1; i <= n; i ++ ) arr[i] = rmin[i][col];
        get_min(arr, resmin, n, a);
        
        for (int i = 1; i <= n; i ++ ) arr[i] = rmax[i][col];
        get_max(arr, resmax, n, a);
        
        for (int i = a; i <= n; i ++ )
            ans = (ans + (LL)resmin[i] * resmax[i]) % mod;
    }
    
    cout << ans << endl;
    
    return 0;
}