一道单调栈的好题啊。。。。。。
思路是很奇妙的，对于每个点（i，j），我们可以算它对答案的贡献（即包含它的矩形数量），包含该点的矩形，点的高度为h[j]，点右边的高度一定大于等于h[j]，左边的高度一定大于h[j]。
高有h[j]种方案，底边有(j - lj) * (rj - j)种方案,相乘就是该点对答案的贡献。
具体步骤：
1.定义 h[j] 为当前行第 j 列可向上延伸多少（如果当前块被图画那么值为0）
2.使用单调栈算出 li 和 ri ，分别是 j中左边第一个（从 j 开始）不大于 h[j] 的数和右边第一个（从 j 开始）小于 h[j] 的数
3.(j-lj)*(rj-j)*h[j]的值就是每一个点所能组成的矩形的个数。
1 #include<bits/stdc++.h>
2 using namespace std;
3 char ch;
4 long long l[1020],r[1020],h[1020],k[1020],n,m,top;
5 int d[1020][1020];
6 long long ans;
7
8 void ddzl(){//左
9 top=0;
10 for(int i=m;i>=1;i--){
11 while(top!=0 && h[i]<=h[k[top]]) l[k[top--]]=i;
12 k[++top]=i;
13 }
14 while(top) l[k[top--]]=0;
15 }
16
17 void ddzr(){//右
18 top=0;
19 for(int i=1;i<=m;i++){
20 while(top!=0 && h[i]<h[k[top]]) r[k[top--]]=i;
21 k[++top]=i;
22 }
23 while(top) r[k[top--]]=m+1;
24 }
25
26 void work(){
27 ddzl();//求左边第一个小等于的下标
28 ddzr();//求右边第一个小于的下标
29 for(int i=1;i<=m;i++)
30 ans+=(i-l[i])*(r[i]-i)*h[i];//累加结果
31 }
32
33 int main(){
34 cin>>n>>m;
35 for(int i=1;i<=n;i++)
36 for(int j=1;j<=m;j++){
37 cin>>ch;
38 if(ch=='*') d[i][j]=1;//标记
39 }
40 for(int i=1;i<=n;i++){
41 for(int j=1;j<=m;j++){
42 h[j]++;
43 if(d[i][j]) h[j]=0;//求该列从最上面到j的最大延伸高度
44 }
45 work();//对每一行累加结果
46 }
47 cout<<ans;
48 }
（单调栈其实不好想啊，难点在于推公式，公式的意义就是每个点对答案的贡献，公式想到了，自然也能想到用单调栈维护）。
