题意

给你一个01矩阵，问你有i*j的全1矩阵有多少个

前言

这题肝了很久
主要是受到惯性思维的影响。。
一直没有意识到一个$i*j$的矩阵里面包含了两个$i*(j-1)$的矩阵
真是失了智，一个早上就被浪费了

题解

我们考虑，我们只要左右能扩展最远的极大子矩阵
这个用一个单调栈来维护即可
这个差分一下就可以做到$O(nm)$
然后得到了左右能扩展最远的极大子矩阵后，他里面的更小的矩阵，则要加上
较暴力的写法是这样的

for (int i=1;i<=m;i++)for (int j=i+1;j<=m;j++)ans[u][i]=ans[u][i]+ans[u][j]*(j-i+1);

但是这样是$O(n^3)$的
但其实仔细观察一下，就可以优化为$O(n^2)$了

整体思路不难，就是用一个单调栈先求出左右能扩展最远的极大子矩阵
但是由于我比较SB还是做了很久。。
CODE:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int N=605;
int n,m;
char ss[N];
int h[N];
int sta[N],top;
int read ()
{char ch=getchar();int x=0;while (ch<'0'||ch>'9') ch=getchar();while (ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}return x;
}
inline void out(int x)
{int len=0;char ss[10];if(!x){
   putchar('0');return;}while(x)ss[len++]=x%10,x/=10;while(len)putchar(ss[--len]+48);
}
int ans[N][N];int main()
{n=read();m=read();for (int u=1;u<=n;u++){scanf("%s",ss+1);top=0;for (int i=1;i<=m+1;i++){h[i]=ss[i]=='1'?h[i]+1:0;//printf("%d ",h[i]);while (top>0&&h[sta[top]]>h[i]){//printf("%d %d %d\n",max(h[sta[top-1]],h[i]),h[sta[top]]+1,i-sta[top-1]-1);ans[max(h[sta[top-1]],h[i])+1][i-sta[top-1]-1]++;ans[h[sta[top]]+1][i-sta[top-1]-1]--;top--;}while (top>0&&h[sta[top]]==h[i]) top--;sta[++top]=i;}}for (int u=1;u<=n;u++)for (int i=1;i<=m;i++)ans[u][i]=ans[u][i]+ans[u-1][i];for (int u=1;u<=n;u++){int sum=0,lalal=0;for (int i=2;i<=m;i++){lalal=lalal+ans[u][i];sum=sum+ans[u][i]*i;}for (int i=1;i<=m;i++){ans[u][i]=ans[u][i]+sum;sum=sum-lalal-ans[u][i+1];lalal=lalal-ans[u][i+1];}/*for (int i=1;i<=m;i++){for (int j=i+1;j<=m;j++)ans[u][i]=ans[u][i]+ans[u][j]*(j-i+1);}*/}for (int u=1;u<=n;u++){for (int i=1;i<=m;i++){out(ans[u][i]);putchar(' ');}putchar('\n');}return 0;
}