用单调栈的话不严格的O(n^3)可以轻松艹过去，统计的时候要差分。
可以发现，对于一个单调栈里的元素，从它进栈到出栈都会重复类似的计算。。再差分一波后就可以只在出栈的时候计算一下了。
具体的话看代码吧。。
O(n^3):
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#define ll long long
#define ui unsigned int
#define ull unsigned long long
using namespace std;
const int maxn=;
char s[maxn];
int h[maxn],st[maxn],l[maxn];
int an[maxn][maxn];
int i,j,k,n,m; int ra,fh;char rx;
inline int read(){
rx=getchar(),ra=,fh=;
while((rx<''||rx>'')&&rx!='-')rx=getchar();
if(rx=='-')fh=-,rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra*fh;
}
inline void add(int y1,int x2,int y2){
// printf("add:1,%d %d,%d\n",y1,x2,y2);
an[x2][y2]++,an[x2][y1-]--;
}
inline void addall(int len,int st2,int h){
for(register int i=;i<=len;i++)an[h][i+st2]++,an[h][i-]--;
// add(i,h,i+st2);
// an[h][1+st2]++,an[h][len+st2+1]--,
// an[h][0]--,an[h][len]++;
} char ss[];int len;
inline void outx(int x){
if(!x){putchar('');return;}
while(x)ss[len++]=x%,x/=;
while(len)putchar(ss[--len]+);
}
int main(){
n=read(),m=read();//register int k;
for(i=;i<=n;i++){
scanf("%s",s+);
int top=;
for(j=;j<=m+;j++){
h[j]=s[j]==''?h[j]+:;
while(top&&h[st[top]]>=h[j])addall(j-st[top],st[top]-l[top],h[st[top]]),top--;
st[++top]=j,l[top]=st[top-]+;
//for(k=1;k<=top;k++)add(j-st[k]+1,h[st[k]],j-l[k]+1);
}
}
// for(i=1;i<=n;i++)for(j=1;j<=m;j++)an[i][j]+=an[i][j-1];
// for(i=1;i<=n;printf("%d\n",an[i][m]),i++)for(j=1;j<m;j++)printf("%d ",an[i][j]);
for(i=n;i;i--)for(j=m;j;j--)an[i][j]+=an[i+][j]+an[i][j+]-an[i+][j+];
for(i=;i<=n;outx(an[i][m]),putchar('\n'),i++)for(j=;j<m;j++)outx(an[i][j]),putchar(' ');
}
O(n^2):
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#define ll long long
#define ui unsigned int
#define ull unsigned long long
using namespace std;
const int maxn=;
char s[maxn];
int h[maxn],st[maxn],l[maxn];
int an[maxn][maxn];
int i,j,k,n,m; int ra,fh;char rx;
inline int read(){
rx=getchar(),ra=,fh=;
while((rx<''||rx>'')&&rx!='-')rx=getchar();
if(rx=='-')fh=-,rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra*fh;
} inline void addall(int len,int st2,int h){
an[h][+st2]++,an[h][len+st2+]--,
an[h][]--,an[h][len]++;
} char ss[];int len;
inline void outx(int x){
if(!x){putchar('');return;}
while(x)ss[len++]=x%,x/=;
while(len)putchar(ss[--len]+);
}
int main(){
n=read(),m=read();register int i,j;
for(i=;i<=n;i++){
scanf("%s",s+);
int top=;
for(j=;j<=m+;j++){
h[j]=s[j]==''?h[j]+:;
while(top&&h[st[top]]>=h[j])addall(j-st[top],st[top]-l[top],h[st[top]]),top--;
st[++top]=j,l[top]=st[top-]+;
}
}
for(i=;i<=n;i++)for(j=;j<=m;j++)an[i][j]+=an[i][j-];
for(i=;i<=n;i++)an[i][m+]=;for(i=;i<=m;i++)an[n+][i]=;
for(i=n;i;i--)for(j=m;j;j--)an[i][j]+=an[i+][j]+an[i][j+]-an[i+][j+];
for(i=;i<=n;outx(an[i][m]),putchar('\n'),i++)for(j=;j<m;j++)outx(an[i][j]),putchar(' ');
}