用 滑动窗口 算法 解决 蓝桥杯子矩阵 的运行超时 问题

#include<bits/stdc++.h>

using namespace std;

int main()

{

//输入

int n, m, a, b, ans = 0;

cin >> n >> m >> a >> b;

deque < int > Q;

//J --矩阵，，MIN--最小值，，MAX--最大值，，MIN_n--n行最小值，，MAX_n--n行最大值

vector < vector<int> >J(n, vector<int>(m));

vector < vector<int> >MIN_n(n, vector<int>(m - b + 1));

vector < vector<int> >MIN(n - a + 1, vector<int>(m - b + 1));

vector < vector<int> >MAX_n(n, vector<int>(m - b + 1));

vector < vector<int> >MAX(n - a + 1, vector<int>(m - b + 1));

for (int i = 0; i < n; i++)

for (int j = 0; j < m; j++)

cin >> J[i][j];

//构造MIN_n和MAX_n

for (int i = 0; i < n; i++) {

for (int j = 0; j < m; j++) {

if (!Q.empty() && j - Q.front() + 1 > b) Q.pop_front();//队列中有元素且滑动窗口的大小超过了b，则出队

while (!Q.empty() && J[i][Q.back()] >= J[i][j]) Q.pop_back();//如果进队元素破坏了队列单调性，则r--

Q.emplace_back(j);//正常进队

if (j >= b - 1) MIN_n[i][j - b + 1] = J[i][Q.front()];//提取出最小值

}

Q.clear();

for (int j = 0; j < m; j++) {

if (!Q.empty() && j - Q.front() + 1 > b) Q.pop_front();

while (!Q.empty() && J[i][Q.back()] <= J[i][j]) Q.pop_back();

Q.emplace_back(j);

if (j >= b - 1) MAX_n[i][j - b + 1] = J[i][Q.front()];

}

Q.clear();

}

//构造MIN和MAX

for (int i = 0; i < m - b + 1; i++) {

for (int j = 0; j < n; j++) {

if (!Q.empty() && j - Q.front() + 1 > a) Q.pop_front();

while (!Q.empty() && MIN_n[Q.back()][i] >= MIN_n[j][i]) Q.pop_back();

Q.emplace_back(j);

if (j >= a - 1) MIN[j - a + 1][i] = MIN_n[Q.front()][i];

}

Q.clear();

for (int j = 0; j < n; j++) {

if (!Q.empty() && j - Q.front() + 1 > a) Q.pop_front();

while (!Q.empty() && MAX_n[Q.back()][i] <= MAX_n[j][i]) Q.pop_back();

Q.emplace_back(j);

if (j >= a - 1) MAX[j - a + 1][i] = MAX_n[Q.front()][i];

}

Q.clear();

}

//计算价值和

for (int i = 0; i < n - a + 1; i++)

for (int j = 0; j < m - b + 1; j++)

ans += MIN[i][j] * MAX[i][j];

cout << ans % 998244353;

return 0;

}