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

一、视频讲解

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

二、正解代码

//二维单调队列
#include
#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();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111