蓝桥杯2023年第十四届省赛真题-子矩阵-multiset维护最最值

解题思路:

思路总结一下吧：第一步：算每个（（行）a*（列）1）的最小值。

                          第二步，再增加列数，当列数达到b的时候这样就构成了一个（a*b）的矩阵，这样就可以得出一个矩阵的最小值。以此类推。

                          最大值同样道理

注意事项:1..multiset定义排序规则需要用类实现

               2.每次进入新行需要清空排序容器 
参考代码:

#include<iostream>
#include<vector>
#include<set>
using namespace std;
#define ll long long
const int N=1010,mod=998244353;
int n,m,a,b;
ll w[N][N];
ll lmin[N][N],lmax[N][N];
class cmp{
	public:
	bool operator()(ll x,ll y) {
	return x>y;
	}
};
vector<ll>ansmin;
vector<ll>ansmax;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>a>>b;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	cin>>w[i][j];
    //计算以a为行数的，1为列数的所有列条的最小值 
    multiset<ll>p;
    for(int j=1;j<=m;j++)
       for(int i=1;i<=n;i++){
       	if(i==1) p.clear();
       	p. insert(w[i][j]);
		   //先删除最顶端的不在范围内的那个值，再去取最小值 
		   if(i>a){
		    	p.erase(*p.find(w[i-a][j]));
			}
       	    if(i>=a) {
       	  	  lmin[i-a+1][j]=*p.begin();
			 }
	   }
	   //计算以a为行数的，1为列数的所有列条的最大值
	   multiset<ll,cmp>q;
	   for(int j=1;j<=m;j++)
       for(int i=1;i<=n;i++){
       		if(i==1) q.clear();	
			   q. insert(w[i][j]);
		   //先删除最顶端的不在范围内的那个值，再去取最小值 
		   if(i>a){
		    	q.erase(*q.find(w[i-a][j]));
			}
       	    if(i>=a) {
       	  	  lmax[i-a+1][j]=*q.begin();
			 }
	   }
	   vector<ll>ansmin;
	   multiset<ll>x; 
	   //搜索每个二维区间的最小值 
	   for(int i=1;i<=n;i++)
	   for(int j=1;j<=m;j++){
	   	 //算下一行需要更新排序容器，防止上一行后面的残留数据影响当前新的矩阵的最值判断
			if(j==1) x.clear(); 
			x.insert(lmin[i][j]);
			if(j>b){
				x.erase(*x.find(lmin[i][j-b]));
			} 
			if(j>=b){
			//这要的是以（i，j)为左上顶点的以a*b为矩阵的最小值
				ansmin.push_back(*x.begin());
			}
	   }  
	    vector<ll>ansmax;
	    multiset<ll,cmp>y;
	    //搜索每个二维区间的最大值 
	   for(int i=1;i<=n;i++)
	   for(int j=1;j<=m;j++){
	   	        //算下一行需要更新排序容器，防止上一行后面的残留数据影响当前新的矩阵的最值判断
			if(j==1) y.clear(); 
			y.insert(lmax[i][j]);
			if(j>b){
			 //这要的是以（i，j)为左上顶点的以a*b为矩阵的最大值
				y.erase(*y.find(lmax[i][j-b]));
			} 
			if(j>=b){
				ansmax.push_back(*y.begin());
			}
	   } 
	   //算最后的结果，由于数据量的一致性，所以两个存放最大值和最小值的容器大小一致 
	   ll ans=0;
	   for(int i=0;i<ansmin.size();i++) 
	   ans=(ans+(ansmin[i]%mod)*ansmax[i]%mod)%mod;
	   cout<<ans;
	return 0;
}