题目描述

萌萌哒的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，表示这个格子被破坏；反之代表这个格子是完好无损的。

输出格式：

仅一个正整数，表示未被破坏的子矩阵的个数。

输入输出样例

3 41 1 1 11 0 1 11 1 0 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    无

比赛时想了一个做法，然而有巨大漏洞没有发现，结果只得10分但至少发现了以(i,j)为右下角高h长l的矩形里矩形个数为h*l，没有右下角限制就是(1+...+h）＊（1+...+L）

正解好厉害，也是考虑求每个(i,j)为右下角的矩阵个数
一行一行的求，tot[j]表示j列连续1有几个
每一行用一个单调栈维护（每一列）矩阵的h和l，如果栈顶的h比当前大，就把栈顶和当前合并，l相加，cnt减去栈顶贡献
最后cnt是累加的，因为这时cnt保存的这一行h<当前的矩阵，当然也可以到达(i,j)，也有这一块贡献

#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;typedef long long ll;const int N=3e3+5;inline int read(){    char c=getchar();int x=0,f=1;    while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}    while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();}    return x;}int n,m,a[N][N],tot[N];//tot---> liell ans=0;struct data{int h,l;}st[N];int top=0;int main(){    n=read();m=read();    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) a[i][j]=read();    for(int i=1;i<=n;i++){        ll cnt=0;        top=0;        data tmp;        for(int j=1;j<=m;j++){            if(!a[i][j]){tot[j]=0;cnt=0;top=0;continue;}            tmp.h=++tot[j];tmp.l=1;            while(top&&st[top].h>=tmp.h){                tmp.l+=st[top].l;                cnt-=st[top].h*st[top].l;                top--;            }            st[++top]=tmp;            cnt+=tmp.h*tmp.l;            //printf("%d %d %lld\n",i,j,cnt);            ans+=cnt;        }    }    printf("%lld",ans);}

洛谷10月月赛Round.1| P3400 仓鼠窝[单调栈]