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

 标题

 

代码

1. #include <bits/stdc++.h>
2. using namespace std;
3. typedef long long ll;
4. const int N = 1010, mod = 998244353;
5. int g[N][N];
6. int rmin[N][N], rmax[N][N];
7. ll mmin[N][N], mmax[N][N];
8. int q[N * N];
9. int hh, tt;
10. int n, m, a, b;
11. int main()
12. {
13.   cin >> n >> m >> a >> b;
14.   for (int i = 1; i <= n; i++)
15.   {
16.     for (int j = 1; j <= m; j++)
17.     {
18.       cin >> g[i][j];
19.     }
20.   }
22.   for (int i = 1; i <= n; i++)
23.   {
24.     hh = 0, tt = -1;
25.     for (int j = 1; j <= m; j++)
26.     {
27.       if (hh <= tt && j - q[hh] + 1 > b)
28.         hh++;
29.       while (hh <= tt && g[i][q[tt]] >= g[i][j])
30.         tt--;
31.       q[++tt] = j;
32.       if (j >= b)
33.         rmin[i][j - b + 1] = g[i][q[hh]];
34.     }
35.   }
37.   for (int j = 1; j <= m; j++)
38.   {
39.     hh = 0, tt = -1;
40.     for (int i = 1; i <= n; i++)
41.     {
42.       if (hh <= tt && i - q[hh] + 1 > a)
43.         hh++;
44.       while (hh <= tt && rmin[q[tt]][j] >= rmin[i][j])
45.         tt--;
46.       q[++tt] = i;
47.       if (i >= a)
48.         mmin[i - a + 1][j] = rmin[q[hh]][j];
49.     }
50.   }
52.   for (int i = 1; i <= n; i++)
53.   {
54.     hh = 0, tt = -1;
55.     for (int j = 1; j <= m; j++)
56.     {
57.       if (hh <= tt && j - q[hh] + 1 > b)
58.         hh++;
59.       while (hh <= tt && g[i][q[tt]] <= g[i][j])
60.         tt--;
61.       q[++tt] = j;
62.       if (j >= b)
63.         rmax[i][j - b + 1] = g[i][q[hh]];
64.     }
65.   }
67.   for (int j = 1; j <= m; j++)
68.   {
69.     hh = 0, tt = -1;
70.     for (int i = 1; i <= n; i++)
71.     {
72.       if (hh <= tt && i - q[hh] + 1 > a)
73.         hh++;
74.       while (hh <= tt && rmax[q[tt]][j] <= rmax[i][j])
75.         tt--;
76.       q[++tt] = i;
77.       if (i >= a)
78.         mmax[i - a + 1][j] = rmax[q[hh]][j];
79.     }
80.   }
82.   ll ans = 0;
83.   for (int i = 1; i + a - 1 <= n; i++)
84.   {
85.     for (int j = 1; j + b - 1 <= m; j++)
86.     {
87.       ans = (ans + (mmin[i][j] * mmax[i][j]) % mod) % mod;
88.     }
89.   }
91.   cout << ans;
92. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。