蓝桥杯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;
}