蓝桥杯2023年第十四届省赛真题-子矩阵 (优先队列，C++代码)

解题思路:
        考虑将问题划分为两个部分，第一部分为求以nums[i][j]为顶点向下扩展a个元素的最大最小值。第二部分是通过之前求出的nums[i][j]从左到右的形式扩招。求第一部分考虑每一列都维护一个大根堆和一个小根堆，将每一列的元素插入大根堆和小根堆中，不断往下移动，并将新元素入堆，然后不断检测堆顶元素是否出界，将出界的元素删除掉，并在每一次完成大根堆和小根堆的维护后将列向量的最大值和最小值插入nums数组中，这样就可以得到所有列向量的最大最小元素。时间复杂度约为n^2。在获得nums数组以后也是重复上述类似操作，设置一个大根堆和一个小根堆，以nums的最大值最小值为元素入堆，并将出界的元素删除掉，注意要在完成一行以后清空两个堆。
注意事项:
        1.注意取模操作

        2.注意完成一行以后清空堆

        3.注意下标是否越界

参考代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
struct point{
	ll val;
	int x;
	int y;
	bool operator > (point t) const{
		return val >= t.val;
	}
	bool operator < (point t) const{
		return val <= t.val;
	} 
};
struct num{
	int maxn;
	int minn;
};
const int N = 1010;
ll f[N][N];
num nums[N][N];
int n,m,a,b;
void init(){
	priority_queue<point, vector<point>,greater<point>> Q[N];
	priority_queue<point, vector<point>,less<point>> M[N];
	for(int i=1;i<=m;i++){
		for(int j=1;j<=a;j++){
			Q[i].push({f[j][i],i,j});
			M[i].push({f[j][i],i,j});
		} 
		nums[1][i].maxn = M[i].top().val;
		nums[1][i].minn = Q[i].top().val;
	} 
	for(int i=1;i<=m;i++){
		for(int j=2;j<=n-a+1;j++){
			Q[i].push({f[j+a-1][i],i,j+a-1});
			M[i].push({f[j+a-1][i],i,j+a-1});
			while(Q[i].top().y < j){
				Q[i].pop();
			}
			while(M[i].top().y < j){
				M[i].pop();
			}	
			nums[j][i].maxn = M[i].top().val;
			nums[j][i].minn = Q[i].top().val;
		}
	}
	
}
int main(){
	ll res = 0;
	priority_queue<point, vector<point>,greater<point>> Q;
	priority_queue<point, vector<point>,less<point>> M;
	cin>>n>>m>>a>>b;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>f[i][j];
		}
	}
	init();	
	
	for(int i = 1;i<=n-a+1;i++){
		for(int j=1;j<=b;j++){
			Q.push({nums[i][j].minn,j,i});
			M.push({nums[i][j].maxn,j,i});
		}
		res += (Q.top().val * M.top().val)%mod;
		for(int j=2;j<=m-b+1;j++){
			Q.push({nums[i][j+b-1].minn,j+b-1,i});
			M.push({nums[i][j+b-1].maxn,j+b-1,i});
			while(Q.top().x < j){
				Q.pop();
			}
			while(M.top().x < j){
				M.pop();
			}
	
			res += (Q.top().val * M.top().val)%mod;
		}
		while(!Q.empty()){
			Q.pop();
		}
		while(!M.empty()){
			M.pop();
		}
	}
	cout<<res%mod<<endl;
	
	return 0;
}