题目 3161: 蓝桥杯2023年第十四届省赛真题-子矩阵

 题目

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1010, mod = 998244353;
int g[N][N];
int rmin[N][N], rmax[N][N];
ll mmin[N][N], mmax[N][N];
int q[N * N];
int hh, tt;
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 >> g[i][j];}}for (int i = 1; i <= n; i++){hh = 0, tt = -1;for (int j = 1; j <= m; j++){if (hh <= tt && j - q[hh] + 1 > b)hh++;while (hh <= tt && g[i][q[tt]] >= g[i][j])tt--;q[++tt] = j;if (j >= b)rmin[i][j - b + 1] = g[i][q[hh]];}}for (int j = 1; j <= m; j++){hh = 0, tt = -1;for (int i = 1; i <= n; i++){if (hh <= tt && i - q[hh] + 1 > a)hh++;while (hh <= tt && rmin[q[tt]][j] >= rmin[i][j])tt--;q[++tt] = i;if (i >= a)mmin[i - a + 1][j] = rmin[q[hh]][j];}}for (int i = 1; i <= n; i++){hh = 0, tt = -1;for (int j = 1; j <= m; j++){if (hh <= tt && j - q[hh] + 1 > b)hh++;while (hh <= tt && g[i][q[tt]] <= g[i][j])tt--;q[++tt] = j;if (j >= b)rmax[i][j - b + 1] = g[i][q[hh]];}}for (int j = 1; j <= m; j++){hh = 0, tt = -1;for (int i = 1; i <= n; i++){if (hh <= tt && i - q[hh] + 1 > a)hh++;while (hh <= tt && rmax[q[tt]][j] <= rmax[i][j])tt--;q[++tt] = i;if (i >= a)mmax[i - a + 1][j] = rmax[q[hh]][j];}}ll ans = 0;for (int i = 1; i + a - 1 <= n; i++){for (int j = 1; j + b - 1 <= m; j++){ans = (ans + (mmin[i][j] * mmax[i][j]) % mod) % mod;}}cout << ans;
}