P3400 仓鼠窝
题目描述
萌萌哒的Created equal是一只小仓鼠，小仓鼠自然有仓鼠窝啦。
仓鼠窝是一个由n*m个格子组成的行数为n、列数为m的矩阵。小仓鼠现在想要知道，这个矩阵中有多少个子矩阵！（实际上就是有多少个子长方形嘛。）比如说有一个2*3的矩阵，那么1*1的子矩阵有6个，1*2的子矩阵有4个，1*3的子矩阵有2个，2*1的子矩阵有3个，2*2的子矩阵有2个，2*3的子矩阵有1个，所以子矩阵共有6+4+2+3+2+1=18个。
可是仓鼠窝中有的格子被破坏了。现在小仓鼠想要知道，有多少个内部不含被破坏的格子的子矩阵！
输入输出格式
输入格式：
第一行两个正整数n和m，分别表示仓鼠窝的行数n、列数m。
接下来n行，每行m个数，每个数代表对应的格子，非0即1。若为0，表示这个格子被破坏；反之代表这个格子是完好无损的。
输出格式：
仅一个正整数，表示未被破坏的子矩阵的个数。
输入输出样例
输入样例#1：
3 4
1 1 1 1
1 0 1 1
1 1 0 1
输出样例#1：
26
说明
__本题时限2s，内存限制256M，因新评测机速度较为接近NOIP评测机速度，请注意常数问题带来的影响。__
No n= m= 备注
1 2 2 无
2 3 3 无
3 5 5 无
4 10 10 无
5 2000 2000 所有格子均未被破坏
6 3000 3000 所有格子均未被破坏
7 2500 3000 有且仅有一个格子被破坏
8 3000 2500 有且仅有一个格子被破坏
9 200 200 无
10 500 500 无
11 500 500 无
12 500 500 无
13 1000 1000 无
14 1000 1000 无
15 1000 1500 无
16 2500 2500 无
17 2500 3000 无
18 3000 2500 无
19 3000 3000 无
20 3000 3000 无
/*
对于每个点，累加高度，看能往右扩展几步。
单调栈实现 栈内元素是每个点能扩展的高度，单调递增
如果当前元素的高度大于栈顶元素的高度，就可以累加宽度并入栈
否则就出栈知道大于为止，这样才可以累加宽度
类似这种情况
****
***
**
*
如果入栈的高度为3，那么一定不能合并第4列的宽度，因为构不成矩形。
每次入栈的时候合并宽度
pair里分别存的是高度和宽度
*/
#include<iostream>
#include<cstdio>
#include<cstring> #define N 3007
#define ll long long using namespace std;
int n,m,k,top;
int a[N][N],tot[N];
ll ans,cnt;
pair<int,int>sta[N]; inline int read()
{
int x=,f=;char c=getchar();
while(c>''||c<''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
} int main()
{
n=read();m=read();
for(int i=;i<=n;i++) for(int j=;j<=m;j++)
a[i][j]=read(); for(int i=;i<=n;i++)
{
cnt=;top=;pair<int,int>tmp;
for(int j=;j<=m;j++)
{
if(a[i][j]==)
{
cnt=top=;tot[j]=;
continue;
}
tot[j]++;tmp.first=tot[j];tmp.second=;
while(top && sta[top].first>=tmp.first)
{
tmp.second+=sta[top].second;//合并到一起，宽度++
cnt-=sta[top].first*sta[top--].second;//此部分会在下面重复计算所以减去
}
sta[++top]=tmp;
cnt+=tmp.first*tmp.second;ans+=cnt;//当前结果就等于入栈的那个点的计算结果
}
}
printf("%lld\n",ans);
return ;
}