6.26 子矩阵

简单题意，求出一个矩阵中所有子矩阵最小值的和

乍一看很麻烦，暴力也需要考虑很多的情况，不太好弄

分析如下：

矩阵一定是矩形，如果某个元素是所在矩阵的最小值，那么在这个矩阵的范围内，它是他所在行与列的最小值，这样就能解决了。

首先枚举出分行的情况，并且递推算出其中每一列的最小值，用一个数组记录。

然后向左向右分别维护一个单调栈，也就是确定所求元素的左右可到达的边界

之后使用公式ans[mi[k]]+=(k-L[k]+1)*(R[k]-k+1)进行累加（mi数组记录第k列的最小值，r[k]与l[k]存储左右边界）;

由于枚举了所有的分行的情况，所以不存在漏算的情况

而每一行也尽可能达到了左右边界，所以也不存在少算的地方

以样例来演算一遍：

2 3

2 5 1

6 3 4

分行[1,1]的情况

第一列最小值为2，第二列最小值5，第三列最小值1 m[1]=2,m[2]=5,m[3]=1;

第一列的2显然比第三列的1要小，所以R[1]只能取到2

第二列的5比临近的两个元素都要小，R[2]与L[2]都是2

第三列的1是最小的，L[3]=1,R[3]=3

这样，ans[2]+=(1-1+1)*(2-1+1)

ans[5]+=(2-2+1)*(2-2+1)

ans[1]+=(3-1+1)*(3-3+1)

之后继续枚举各种分行的情况就好了

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int inf=1<<30;
int n,m,i,j,k,top;
int a[305][305],mi[305],L[305],R[305];
int ans[100005],stack[305];
int min(int x,int y)
{
    if(x<y) return x;
    else return y;
} 
int main()
{
    scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++) scanf("%d",&a[i][j]);
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++) mi[j]=inf;
        for(k=1;k<=m;k++) mi[k]=min(mi[k],a[j][k]);
        for(j=i;j<=n;j++)
        {
            for(k=1;k<=m;k++)
            {
                while(top&&mi[k]<mi[stack[top]])
                {
                    R[stack[top]]=k-1;
                    --top;
                }
                stack[++top]=k;
            }
            while(top)
            {
                R[stack[top]]=m;
                top--;
            }
            for(k=m;k>=1;k--)
            {
                while(top&&mi[k]<mi[stack[top]])
                {
                    L[stack[top]]=k+1;
                    --top;
                }
                stack[++top]=k;
            }
            while(top)
            {
                L[stack[top]]=1;
                --top;
            }
            for(k=1;k<=m;k++) ans[mi[k]]+=(k-L[k]+1)*(R[k]-k+1);
        }
    }
    for(i=1;i<=n*m;i++) printf("%d
",ans[i]);
    return 0;
}