蓝桥杯真题讲解：子矩阵（二维滑动窗口）
- 一、视频讲解
- 二、正解代码
一、视频讲解
蓝桥杯真题讲解：子矩阵（二维滑动窗口）
二、正解代码
//二维单调队列#include#define endl '\n'#define deb(x) cout << #x << " = " << x << '\n';#define INF 0x3f3f3f3f#define int long longusing 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();}