一、视频讲解

蓝桥杯真题讲解：子矩阵（二维滑动窗口）

二、正解代码

//二维单调队列
#include<bits/stdc++.h>
#define endl '\n'
#define deb(x) cout << #x << " = " << x << '\n';
#define INF 0x3f3f3f3f
#define int long long
using namespace std;
const int mod =  998244353;
const int N = 1e3 + 10;
int g[N][N];
int q[N];
int line_max[N][N], line_min[N][N];
int maxv[N][N], minv[N][N];
int a, b, n, m;void solve()
{cin >> n >> m >> a >> b;for(int i = 0; i < n; i ++)for(int j = 0; j < m; j ++)cin >> g[i][j];//求出每一行的滑动窗口for(int i = 0; i < n; i ++){int h = 0, t = -1;for(int j = 0; j < m; j ++){if(h <= t and q[h] < j - b + 1){h ++;}while(h <= t and g[i][q[t]] <= g[i][j])t--;q[++t] = j;if(j - b + 1 >= 0){line_max[i][j - b + 1] = g[i][q[h]];}}}//对每一行的滑动窗口求一遍滑动窗口for(int j = 0; j < m; j ++){int h = 0, t = -1;for(int i = 0; i < n; i ++){if(h <= t and q[h] < i - a + 1){h ++;}while(h <= t and line_max[q[t]][j] <= line_max[i][j])t --;q[++t] = i;if(i - a + 1 >= 0)maxv[i - a + 1][j] = line_max[q[h]][j];}}//求最小值//先针对每一行，求出每一行的滑动窗口。for(int i = 0; i < n; i ++){int h = 0, t = -1;for(int j = 0; j < m; j ++){if(h <= t and q[h] < j - b + 1){h ++;}while(h <= t and g[i][q[t]] >= g[i][j])t --;q[++ t] = j;if(j - b + 1 >= 0)line_min[i][j - b + 1] = g[i][q[h]]; }}//针对每一列的滑动黑窗口，求滑动窗口。for(int j = 0; j < m; j ++){int h = 0, t = -1;for(int i = 0; i < n; i ++){if(h <= t and q[h] < i - a + 1){h ++;}while(h <= t and line_min[q[t]][j] >= line_min[i][j])t --;q[++ t] = i;if(i - a + 1 >= 0)minv[i - a + 1][j] = line_min[q[h]][j];}}int ans = 0;for(int i = 0; i < n; i ++){for(int j = 0; j < m; j ++){ans = (ans + maxv[i][j] * minv[i][j] % mod) % mod;}}cout << ans << endl;}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t = 1;//cin >> t;while(t--)solve();
}