---
title: "子矩阵"
created: 2025-11-28
tags:
  - 算法
---

# 子矩阵

## 题目 [子矩阵](https://www.acwing.com/problem/content/description/4967/)

![[image-b9dad894.png]]

## 思路分析

所有子矩阵里的最大值\*最小值相加 结果模上一个数

其实最麻烦的地方就是怎么求出子矩阵的最大值和最小值

在大矩阵里给定小矩阵的宽和高 其实就类似于一个滑动窗口

![[image-e67327dc.png]]

固定宽 不断在整个宽里滑动

在滑动窗口中求最大值和最小值倒是容易了 就是模版的内容

但模板毕竟是一维的

那想办法把这个二维的转变成一维

![[image-457760d8.png]]

把n行拆分成n个一维的单调队列 可以预处理出来每个宽B高1的矩形的最大值和最小值

那么对于一个高A的矩形 就只需要对这些最大值最小值里面再做一次一维的滑动窗口

就能得到整个宽B高A的矩形的最大值和最小值了

那么要算整个矩形中所有子矩形的面积之和也是顺水推舟了

晕了……这tm只是c组的第4题 …………

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=1010,MOD=998244353;

int w[N][N];//大矩阵

int rmax[N][N],rmin[N][N];//每行窗口为B的最大值和最小值

int q[N];

int n,m,A,B;

void get_max(int a[],int b[],int tot,int k)

{

    int hh=0,tt=-1;

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

    {

        if(hh<=tt && i-q[hh]>=k)

            hh++;

        //求最大 递减区间 若出现向上 出队

        while(hh<=tt && a[i]>=a[q[tt]])

            tt--;

        q[++tt]=i;

        //当前区间的最大值为队头

        b[i] = a[q[hh]];

    }

}

void get_min(int a[],int b[],int tot,int k)

{

    int hh=0,tt=-1;

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

    {

        if(hh<=tt && i-q[hh]>=k)

            hh++;

        //求最小 递增区间 若出现向下 出队

        while(hh<=tt && a[i]<=a[q[tt]])

            tt--;

        q[++tt]=i;

        //当前区间的最大值为队头

        b[i] = a[q[hh]];

    }

}

int main()

{

    scanf("%d%d%d%d", &n, &m, &A, &B);

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

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

            scanf("%d", &w[i][j]);

    //预处理出每一行的rmax和rmin

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

        //大宽度为m 小窗口为B

        get_max(w[i],rmax[i],m,B);

        get_min(w[i],rmin[i],m,B);

    }

    int res = 0;

    //每个窗口里有个最大值和最小值已经求出来了

    //现在对于同一个窗口（固定宽） 要求出所有行的的最大值

    //用temp先把每个窗口的最大值和最小值存住 然后枚举每一行 做一次A的滑动窗口

    //结果就会是整个矩形的最大值和最小值

    //存放在Rectmax和Rectmin中

    int temp[N],Rectmax[N],Rectmin[N];

    for (int i=B-1;i<m;i++)

    {

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

            temp[j]=rmax[j][i];

        get_max(temp,Rectmax,n,A);

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

            temp[j] = rmin[j][i];

        get_min(temp, Rectmin, n, A);

        //把所有矩形的最大值和最小值相乘 累加起来 模上mod 就是答案

        for(int j=A-1;j<n;j++)

            res=(res+(LL)Rectmax[j]*Rectmin[j])%MOD;

    }

    printf("%d\n", res);

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[2-Learning/02-算法/03-刷题理模型/栈与队列相关模型/单调队列/单调队列|单调队列]] 🏠 [[00-刷题理模型]] ➡️ [[最大子序和|最大子序和]]