AcWing 4964.子矩阵

首先就是运用了暴力的思路，能够过个70%的数据，剩下的直接时间超时了，没办法优化了。

讲一下暴力的思路：

其实就是模拟而已，也就是看作想要找的矩阵为一个小窗口，然后不断移动的事而已。

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<cmath> 
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
#include<sstream>
#include<map>
#include<limits.h>
#include<set>
#define MAX 1005
#define int long long
#define _for(i,a,b) for(int i=a;i<(b);i++)
#define ALL(x) x.begin(),x.end()
using namespace std;
vector<int>cunchu;
int arr[MAX][MAX];
signed main() {ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);int n, m;int a, b;cin >> n >> m >> a >> b;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++)cin >> arr[i][j];}int sum = 0;//计算结果int left1 = 1;//这里代表的是对于上界的限制int left2 = a;//代表对于下界的限制int right1 = 1;//代表对于左边的限制int right2 = b;//代表对于右边的限制while (left2 <= n) {cunchu.clear();if (right2 > m){right1 = 1;right2 = b;left2++;left1++;continue;}for (int i = left1; i <= left2; i++) {for (int j = right1; j <= right2; j++) {cunchu.push_back(arr[i][j]);}}sort(cunchu.begin(), cunchu.end());sum += (cunchu.front() * cunchu.back()) % 998244353;right1++;right2++;}cout << sum;return 0;
}

接下来就是优化版本：

这里用的是滑动窗口问题的解决方法，也就是所谓数据结构中的单调队列，这也是需要一些数据结构基础的才能接受的知识点。

思路：单调队列讲究的就是一个单调，我们可以先套用单调队列的模板，可以参考一下y总的模板，作者的模板也是跟y总学的，建议首先理解，然后自己敲出来。

我们想，在给定的大矩阵当中，我们从中随便选一块小矩阵的大小，我们要求它的最大值最小值，如果要是暴力的话，复杂度肯定是n**2，而单调队列可以降到n，在求最值的时候我们尝试用单调队列进行求出。但是，我们以往用的单调队列都是线性的，也就是一维的，但不是二维的，怎么办？这样我们可以换个思路，可以从前面写的那个二维双指针可以知道，我们可以把二维问题变成一维的，也就是说，首先固定两个相对的边界。

假设我们这里就首先固定了左右边界，这个时候列数是不是就是小矩阵的长呢？可以自己画图看一下。这个时候，如果说我们先求出来每一行的最大值，再来求每一列的最小值，这两个过程是不是都是线性的呢？是的，这个时候我们的单调队列才派上用场。

对于每一行的最值求完之后，我们还需要对于这些最值中再求最值，这样才能是小矩阵的最值，所以又需要用一次单调队列，这样虽然麻烦，但是效率却是很高的。OK，核心思路就到这里

上代码：

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<cmath> 
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
#include<sstream>
#include<map>
#include<limits.h>
#include<set>
#define MAX 1005
#define int long long
#define _for(i,a,b) for(int i=a;i<(b);i++)
#define ALL(x) x.begin(),x.end()
using namespace std;
vector<int>cunchu;
int arr[MAX][MAX];//存储的大矩阵
int rmax[MAX][MAX], rmin[MAX][MAX];//对于第i-1行的每一个长度为b的窗口求最大/小值
int q[MAX];//队列
int one[MAX], two[MAX], three[MAX];//用来存储列的最值的
void get_max(int a[], int b[], int total, int qujian) {int front = 0;int rear = -1;for (int i = 0; i < total; i++) {if (front <= rear && q[front] + qujian <= i)front++;//当前队头滑出窗口while (front <= rear && a[q[rear]] <= a[i])rear--;//队尾元素比进来的元素小，那么我们就开始更新q[++rear] = i;if (i >= qujian - 1)//滑动窗口已经完全在数组里面进行滑动了，就开始统计每个窗口的最大值。b[i] = a[q[front]];}
}
void get_min(int a[], int b[], int total, int qujian) {int front = 0;int rear = -1;for (int i = 0; i < total; i++) {if (front <= rear && q[front] <= i - qujian)front++;while (front <= rear && a[q[rear]] >= a[i])rear--;q[++rear] = i;if (i >= qujian - 1)b[i] = a[q[front]];}
}
signed main() {ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);int n, m;int a, b;cin >> n >> m >> a >> b;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++)cin >> arr[i][j];}for (int i = 0; i < n; i++) {get_max(arr[i], rmax[i], m, b);//对于每一行的每一个长度为b的窗口求最大值get_min(arr[i], rmin[i], m, b);//对于每一行的每一个长度为b的窗口求最小值}int count = 0;//用来统计积的和//这里的外循环是对于列的遍历，内循环才是对于行的遍历for (int i = b-1; i < m; i++) {//为什么初值是b-1呢？这个时候窗口的队头才是i=0，初值不是b-1的话，窗口是不满的for (int j = 0; j < n; j++) one[j] = rmax[j][i];//这个时候我们对于每一行的当前窗口的最大值进行存储get_max(one, two, n, a);//这里是对于这些行的最大值再进行求最大值，也就是小矩阵的最大值了for (int j = 0; j < n; j++)one[j] = rmin[j][i];//同理，求最小值get_min(one, three, n, a);for (int j = a - 1; j < n; j++) {//为什么这里用a-1当初值呢？其实也是窗口的问题，如果纵向看，窗口的宽就是a了，如果初值不是a-1，窗口也是不满的count = (count + two[j] * three[j]) % 998244353;//这样就是对于所有小矩阵的最值进行相乘然后相加取模了}}cout << count;return 0;
}