題目來自DOTCPP：

暴力思路（兩個測試點超時）：

題目要求我們求出子矩陣的最大值和最小值的乘積，我們可以枚舉矩陣中的所有點，以這個點為其子矩陣的左上頂點，然后判斷一下能不能構成子矩陣。如果可以，我們在遍歷這個子矩陣，求出子矩陣的最大值和最小值，將它加起來。同時，由于題目告訴我們答案可能非常大，即使我們用long long 類型來存答案，也會溢出。因此，我們答案每次加上子矩陣的最小值和最大值的乘積后，可以對998244353 取模，這樣可以保證最終答案數據不會溢出。

暴力代碼：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1020;int n, m, a, b;
int arr[N][N];signed main(){cin >> n >> m >> a >>b;for(int i =1; i <= n; i++){for(int j = 1; j <= m; j++){cin >> arr[i][j];}}int s = 0;//枚舉矩陣每個點for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){if(i+a-1 > n || j+b-1 > m) continue;int ssmin= 1e9+10, ssmax = -1;//找到矩陣中的最大值和最小值for(int k = i; k <= i+a-1; k++){for(int l = j; l <= j+b-1; l++){int x = arr[k][l];ssmax = max(ssmax, x);ssmin = min(ssmin, x);// cout << ssmin << " " << ssmax << endl;}}s += ssmax * ssmin;//題目說了答案非常大 即使是long long 類型也會溢出//所以我們每次的答案%998244353s = s%998244353;// cout << ssmin << "*" << ssmax << endl;}}cout << s  << endl;return 0;
}

優化思路-滑動窗口+單調隊列：

暴力代碼的思路是枚舉每個點，將這個點當成子矩陣的左上角頂點，然后找到子矩陣最小值和最大值，答案加上最小值和最大值的乘積。我們可以對找到子矩陣的最小值和最大值優化，就不會超時了。

窗口每一次都是從一行的最左邊或每一列的上邊開始出發：

①我們先對矩陣的每一行，讓長度為b的窗口開始滑動，找到這一行的最小值和最大值，賦給該窗口的左頂點。

②我們在對矩陣的每一列，讓長度為a的窗口開始滑動，找到這一列的最小值和最大致，賦給該窗口的上頂點。

③也就是說，左上角這個頂點是這個矩陣的最小值和最大值。

容易錯誤的點：

①對矩陣的每一列操作，是在行處理后，找到最小值或最大值基礎上，在對列進行操作，找到最小值和最大值。而不是對原數組arr，找到原數據的最小值和最大值。

②我們是先對每一行求得子矩陣的最小值和最大值，在這個基礎上，再求每一列的最小值和最大值。因此，每一列的最小值和最大值是我們需要的，我們不能把每一行的最小值和最大值、每一列的最小值和最大值放在一起。我們需要的是每一列的最小值和最大值，要分開存數據。

滑動窗口+單調隊列代碼：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1010;int n, m ,a , b;
int arr[N][N];
//隊列中存的是整數在數組的下標
int q[N]; //數組模擬隊列
int hh ,tt; //隊頭指針 隊尾指針
int ssmax[N][N], ssmax_col[N][N];
int ssmin[N][N], ssmin_col[N][N];signed main(){cin >> n >> m >> a>> b;for(int i = 1; i <=n; i++){for(int j = 1; j <= m; j++){cin >> arr[i][j];}}//最小值-行//窗口的最左邊為該窗口的最小值 for(int i = 1; i <= n; i++){//隊頭指針 隊尾指針 初始化hh = 1, tt = 0;for(int j = 1;j <= m; j++){//保證隊列數組從小到大的單調性while(hh <= tt && arr[i][j] < arr[i][q[tt]]) tt--;//將更小的數覆蓋之前的位置q[++tt] = j;//保證窗口長度不超過bif(j-q[hh]+1 > b) hh ++;//當窗口長度為b時候，最小值付給最左邊位置if(j>=b) ssmin[i][j-b+1] = arr[i][q[hh]];}}//要基于行的操作//最小值-列for(int j = 1; j <= m; j++){hh = 1, tt = 0;for(int i = 1; i <= n; i++){while(hh <= tt && ssmin[i][j] < ssmin[q[tt]][j]) tt--;q[++tt] = i;if(i-q[hh]+1 > a)hh++;if(i >=a)ssmin_col[i-a+1][j] = ssmin[q[hh]][j];}}//最大值-行//窗口的最左邊為該窗口的最大值 for(int i = 1; i <= n; i++){//隊頭指針 隊尾指針 初始化hh = 1, tt = 0;for(int j = 1;j <= m; j++){//保證隊列數組從大到小的單調性while(hh <= tt && arr[i][j] > arr[i][q[tt]]) tt--;//將更大的數覆蓋之前的位置q[++tt] = j;//保證窗口長度不超過bif(j-q[hh]+1 > b) hh ++;//當窗口長度為b時候，最大值付給最左邊位置if(j>=b) ssmax[i][j-b+1] = arr[i][q[hh]];}}//基于行的操作基礎//最大值-列for(int j = 1; j <= m; j++){hh = 1, tt = 0;for(int i = 1; i <= n; i++){while(hh <= tt && ssmax[i][j] > ssmax[q[tt]][j]) tt--;q[++tt] = i;if(i-q[hh]+1 > a)hh++;if(i >=a)ssmax_col[i-a+1][j] = ssmax[q[hh]][j];}}int ans = 0;for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){ans += (ssmin_col[i][j] * ssmax_col[i][j]) % 998244353 ;}}cout << ans % 998244353<< endl;return 0;
}