单调队列

首先，学习的一篇博客https://blog.csdn.net/ljd201724114126/article/details/80663855#commentBox

简单思想

单调队列有单调递增和单调递减两种，一般来讲，队列的队首是整个队列的最大值或最小值

具体步骤：

1. 　若队列为空，将A[i]从队尾入队
2.     若队列不为空，将比A[i]大的元素都从队尾弹出，然后把A[i]入队
3.     若队列不为空且A[i]大于队尾，则直接从队尾把A[i]入队

if(q.empty())
  q.push_back(A[i]);
else if(q.back()>A[i]){
  while((!q.empty())&&q.back()>A[i]){
    q.pop_back();
  }
  q.push_back(A[i]);
}
else
  q.push_back(A[i]);
           

651逛花展

https://www.acwing.com/problem/content/653/ 

原题描述：

博览馆正在展出由世上最佳的 M 位画家所画的图画,你想到博览馆去看这些才华横溢的大师们的作品。

可是，那里的博览馆有一个很奇怪的规定，就是在购买门票时必须说明两个数字，

l和r，代表他要看展览中的第 l 幅至第 r 幅画(包含 l 和 r)之间的所有图画，而门票的价钱就是一张图画一元。

为了看到更多名师的画，你希望入场后可以看到所有名师的图画(至少各一张)。

但是你想要花费最少,现在你需要编写计算机程序,来求出最小花费的的 l 值和 r 值。

输入输出格式

输入格式：

第一行是 N 和 M，分别代表博览馆内的图画总数及这些图画是由多少位名师的画所绘画的。

其后的一行包含 N 个数字，它们都介于 1 和 M 之间，代表该位名师的编号。

输出格式：

l和r(l<=r),中间有一个空格,并且题目保证有解,如果多解,输出l最小的.

输入输出样例

输入样例#1：

12 5

2 5 3 1 3 2 4 1 1 5 4 3

输出样例#1：

2 7

数据范围

30%的数据 N<=200N<=200,M<=20M<=20

60%的数据 N<=104N<=104,M<=1000M<=1000

100%的数据 N<=106N<=106,M<=2000M<=2000

题意分析

就是你要求出一个区间[l,r],使得这个区间中有M张不同画师的名画,要求满足条件下,区间长度要最短.

切记:我们这里的单调条件就是:名画种类递增!

结构梳理

如果说队头名画,在队列中还有另外一副和它同属一个画家,那么显然队头必须抛弃.

对于每一幅名画,它都可以入队.

对于每一个候选区间,如果它所有类型的名画都集齐了,那么我们就要统计区间费用.

dequeSTL版本

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define mk(a,b) make_pair(a,b)
const int N=1e6+5;
int l,r,n,m,a[N],b[N],cnt,ansa=1e9,ansb,ans=1e8;
deque<int> q;
//b数组统计名画种类,q双端队列为单调队列.
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        cin>>a[i];
    for(int i=1; i<=n; i++)
    {
        if (!b[a[i]])//曾经没有出现过
            cnt++;
        //这里特殊注意:因为如果说我们当前区间已经满足题意条件,那么我们后面所有的区间统统都会满足条件,因为我们的出队操作,保证我们必须是名画种类递增.
        q.push_back(i);//名画入选
        b[a[i]]++;
        while(b[a[q.front()]]>=2)//队头名画所代表的画家的画在队列中至少有两幅.
        {
            b[a[q.front()]]--;//队头不要了
            q.pop_front();
        }
        if (cnt>=m && q.back()-q.front()+1<ans)//如果集齐各大名画,同时候选答案区间花费的费用更小.
        {
            ansa=q.front();//l
            ansb=q.back();//r
            ans=q.back()-q.front()+1;//费用
        }
    }
    cout<<ansa<<" "<<ansb<<endl;
    return 0;
}

           

普通单调队列模拟

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define mk(a,b) make_pair(a,b)
const int N=1e6+5;
int head,tail;
int l,r,n,m,a[N],b[N],cnt,ansa=1e9,ansb,ans=1e8;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        cin>>a[i];
    head=1,tail=0;
    for(int i=1; i<=n; i++)
    {
        if (!b[a[i]])//未曾出现过
            cnt++;
        tail++;
        b[a[i]]++;
        while(b[a[head]]>=2)
        {
            b[a[head]]--;
            head++;
        }
        if (cnt>=m && tail-head+1<ans)
        {
            ansa=head;
            ansb=tail;
            ans=tail-head+1;
        }
    }
    cout<<ansa<<" "<<ansb<<endl;
    return 0;
}

           

652 切蛋糕

https://www.acwing.com/problem/content/654/ 

今天是小Z的生日，同学们为他带来了一块蛋糕。这块蛋糕是一个长方体，被用不同色彩分成了NN个相同的小块，每小块都有对应的幸运值。

小Z作为寿星，自然希望吃到的第一块蛋糕的幸运值总和最大，但小Z最多又只能吃M小块(M≤N)(M≤N)的蛋糕。

吃东西自然就不想思考了，于是小Z把这个任务扔给了学OI的你，请你帮他从这N小块中找出连续的k块蛋糕(k≤M)(k≤M)，使得其上的幸运值最大。

输入输出格式

输入格式：

输入文件的第一行是两个整数N,M。分别代表共有N小块蛋糕，小Z最多只能吃M小块。

第二行用空格隔开的N个整数，第i个整数Pi代表第ii小块蛋糕的幸运值。

输出格式：

输出文件只有一行，一个整数，为小Z能够得到的最大幸运值。

输入输出样例

输入样例#1：

5 2

1 2 3 4 5

输出样例#1：

9

输入样例#2：

6 3

1 -2 3 -4 5 -6

输出样例#2：

5

题意分析

一句话题意:就是在长度为N的区间里面,找一个长度为K的区间,要求区间的权值最大!

对于这道题目而言,我们依旧需要按照程序=算法+数据结构的思维考虑,不过这一次我们可以直接发现这道题目需要使用单调队列.

因为我们发现这道题目,具有以下两点性质.

1. 区间最值问题,而且具有滚动的条件,单调队列的特性.

2. 队列性质,这道题目可以看作一个区间队列.

既然这道题目是区间最值,那么我们可以想到要用单调队列,当时有几个问题如下所示.

1. 我们如何利用单调队列优化?

2. 如何找出这道题目的单调性质是上升还是递减?

3. 单调队列入队出队怎么判断?

首先面对第一个问题,对于单调队列优化,我们可以将区间的值,设置为单调队列每一个元素,既然这样的话,那么第二问题,我们也可以迎刃而解,当然是单调递增的序列.

接着面对第三个问题,入队出队判断.

1. 入队:对于入队操作而言,当然也是所有元素都可以入队.

2. 出队:对于出队操作而言,有一点小小的变化.

首先我们发现,只要当前队列中,队头元素的已经老了,或者说当前队列超过了m个元素,那么我们必须将队头出队.

如果我们发现队列中队尾开始无法满足单调递增了,那么显然破坏了单调性质,我们必须将他们出队.

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+100;
int a[N],head,tail,n,m,i,j,k,ans,s[N];
deque<int> q;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
        s[i]=s[i-1]+a[i];
    }
    q.push_back(0);//感谢楼下的大佬们.
    for(int i=1; i<=n; i++)
    {
        while(q.size() && q.front()<i-m)//元素个数超过了m限制
            q.pop_front();
        while (q.size() && s[i]<=s[q.back()])//不满足单调递增
            q.pop_back();
        q.push_back(i);//放入队列之中
        if (q.size())//如果队列中有元素
            ans=max(ans,s[i]-s[q.front()]);
    }
    cout<<ans;
    return 0;
}

           

单调队列优化动态规划

题意理解

一个区间的木块要粉刷,每一个木块最多只能粉刷一次,可以不粉刷,对于一个粉刷匠ii而言,他必须粉刷第Si木板,而且只能粉刷一段连续的木块,并且要求粉刷长度不超过Li,而且每刷一个木板,就可以得到Pi的报酬,现在要求报酬最大化, 

尽然如此的话,我们发现K的取值是一个范围,但是我们并不关心这个范围内所有的数值,我们唯一的关心点就是这个范围的最大值.也就是最大的f[i−1][k]

一个区间,最大值,这些关键字眼,不得不让我们思考一下单调队列这种优秀的数据结构.因此我们把中心放到单调队列上面. 

#include <bits/stdc++.h>
using namespace std;
const int M=16000+100;
const int N=110;
int n,m,i,j,k,f[N][M];
struct node
{
    int p,l,s;//单价;最高长度;必备点
} a[M];
deque<int> q;
int cmp(node a,node b)//排序
{
    return a.s<b.s;
}
void init()
{
    ios::sync_with_stdio(false);
    cin>>m>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i].l>>a[i].p>>a[i].s;
    sort(a+1,a+1+n,cmp);
}
int date(int i,int k)
{
    return f[i-1][k]-a[i].p*k;
}
void work()
{
    for(int i=1;i<=n;i++)//粉刷匠
    {
        for(int k=max(0,a[i].s-a[i].l);k<a[i].s;k++)
        {
            while (q.size() && date(i,q.back())<=date(i,k))//不是最优值
                q.pop_back();
            q.push_back(k);
        }
        for(int j=1;j<=m;j++)//粉刷墙
        {
            f[i][j]=max(f[i-1][j],f[i][j-1]);//第一步取最大值
            if (j>=a[i].s)
            {
                while(q.size() && q.front()<j-a[i].l)//不在候选范围内了.
                    q.pop_front();
                if (q.size())
                    f[i][j]=max(f[i][j],a[i].p*j+date(i,q.front()));//计算
            }
        }
    }
    cout<<f[n][m];
}
int main()
{
    init();
    work();
    return 0;
}

           

p2698花盆

https://www.luogu.org/problem/P2698 

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
const int N=1e5+5;
int n;
int q1[N],q2[N],h1,h2,t1,t2,p1[N],p2[N],d;
//q1是最大值队列
//p1是最大值下标队列
//q2是最小值队列
//p2是最小值下标队列
struct node
{
    int x,v;
    bool operator<(node b)
    {
        return x<b.x;
    }
} a[N];
int main()
{
    cin>>n>>d;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i].x>>a[i].v;
    }
    sort(a+1,a+1+n);
    h1=h2=1;
    t1=t2=0;
    int l,r=1,ans=inf;
    for(l=1; l<=n; ++l)
    {
        while(h1<=t1&&p1[h1]<l)//p1是最大值下标队列
            h1++;
        while(h2<=t2&&p2[h2]<l)//p2是最小值下标队列
            h2++;
        for(r; r<=n; r++)
        {
            while(h1<=t1&&q1[t1]<=a[r].v)//q1是最大值队列，维护最大值，保证队列单调递减（所以如果小了就应该删掉），队尾最小
                t1--;
            q1[++t1]=a[r].v;
            p1[t1]=r;
            while(h2<=t2&&q2[t2]>=a[r].v)//q2是最小值队列，维护最小值，保证队列单调递增，队尾最大
                t2--;
            q2[++t2]=a[r].v;
            p2[t2]=r;
            if(q1[h1]-q2[h2]>=d)
            {
                ans=min(ans,a[r].x-a[l].x);
                break;
            }
        }
    }
    cout<<(ans==inf?-1:ans)<<endl;
    return 0;
}
           

最大子序列和

我们先把序列的前i项和加起来并存到一个数组sum[ ]上，那么任意连续的子序列和就为sum [ i ] - sum[ j ] (i>j &&  j>i-m)。

那么我们就可以一直更新就好了，每次找出在（i-m，i）范围内的最小sum[j]值。

代码1：

#include<cstdio>
#include<algorithm>///单调队列，
#include<cstring>
#include<list>
using namespace std;
typedef long long LL;
const int maxn=300010;
LL sum[maxn];
list <int > que;
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        que.clear(); ///清除 
        sum[0]=0;
 
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&sum[i]);
            sum[i]=sum[i-1]+sum[i]; ///求前i项和
        }
        
        ///初始化
        LL maxs=sum[1];
 
        que.push_front(1);
 
        for(int i=2;i<=n;i++)
        {
 
            while(!que.empty()&&i-que.back()>m) ///此步是判断是否在范围（i-m,i)内，不在就pop
                que.pop_back();
 
            maxs=max(maxs,sum[i]-sum[que.back()]); 
                    ///求最大值，sum[i]-sum[min]，表示前i个中找到最小的来减，sum[min]就是单调队列的尾部sum[que.back()]
                    
            while(!que.empty()&&sum[i]<sum[que.front()])  ///更新单调队列，比sum[i]大的值都去掉
                que.pop_front();
 
            que.push_front(i); ///最后将下标i入队
 
        }
        printf("%lld\n",maxs);
    }
    return 0;
}
           

代码2：

#include<cstdio> ///单调递增序列（但保证最可能小）
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const LL maxn=300010;
LL sum[maxn];
LL index1[maxn]; ///存储下标
int main()
{
    LL n,m;
    while(~scanf("%lld%lld",&n,&m))
    {
        sum[0]=0;
        for(int i=1;i<=n;i++){
            scanf("%lld",&sum[i]);
            sum[i]+=sum[i-1]; ///求前i项和
        }
        
        ///初始化
        int left=1,right=1;
        index1[1]=1;
        LL tmax=sum[1];
 
        for(int i=2;i<=n;i++)
        {
            while(index1[left]<i-m) left++; ///不在范围（i-m，i）内，左移就好了
 
            tmax=max(tmax,sum[i]-sum[index1[left]]); ///减去范围（i-m，i）内最小的值
 
            while(right>=left&&sum[i]<sum[index1[right]]) ///排除比值sum[i]大的
                right--;
            right++;
            index1[right]=i; ///将下标添加进去
        }
 
        printf("%lld\n",tmax);
    }
    return 0;
}
           

P2216 [HAOI2007]理想的正方形

https://www.luogu.org/problem/P2216

用单调队列分别维护行与列。

具体实现方法:是先用单调队列对每一行的值维护，并将a[][]每个区间的最大值，最小值分别存在X[][]和x[][]中。

那么X[][]与x[][]所存储的分别是1×n的长方形内的最大值，最小值。X[i][j]存储第i行第j~j+n-1列的长方形中的最大值。同理，x[i][j]存储第i行第j~j+n-1列的长方形中的最小值。

这时再对这两个数组的每一列上的值进行维护，将X[][]中每个区间的的最大值用Y[][]维护，将x[][]中的每个区间的最小值用y[][]维护。那么Y[i][j]存储X[][]中第i~i+n-1行第j列的长方形的最大值。同理y[i][j]存储x[][]中第i~i+n-1行第j列的长方形的最小值。

故Y[i][j]存储的实为以a[i~i+n-1][j~j+n-1]中的最大，即以i,j为左上角，边长为n的正方形中的最大值。同理，y[i][j]存储的即以i,j为左上角，边长为n的正方形中的最小值。

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int a,b,n;
int g[1005][1005];
int Q[1005],q[1005];//用来存最大值最小值的下标的
int X[1005][1005],x[1005][1005];//行的最小最大值
int Y[1005][1005],y[1005][1005];//列的最小最大值
int HEAD,TAIL,head,tail;
int main()
{
    scanf("%d%d%d",&a,&b,&n);
    for(int i=1;i<=a;i++)
    {
        for(int j=1;j<=b;j++)
        {
            scanf("%d",&g[i][j]);
        }
    }
    for(int i=1;i<=a;i++)
    {
        HEAD=TAIL=head=tail=Q[1]=q[1]=1;//先初始化为第一列
        for(int j=2;j<=b;j++)
        {
            //入队操作
            while(HEAD<=TAIL&&g[i][Q[TAIL]]<=g[i][j])//满足递减，最大值
               TAIL--;
            while(head<=tail&&g[i][q[tail]]>=g[i][j])//满足递增，最小值
                tail--;
            TAIL++;
            tail++;
            Q[TAIL]=j;
            q[tail]=j;
            //出队操作
            //如果超过了n,则队首出队
            while(j-Q[HEAD]>=n)
                HEAD++;
            while(j-q[head]>=n)
                head++;
            if(j>=n)
            {
                X[i][j-n+1]=g[i][Q[HEAD]];//以i,j-n+1开头的最大值
                x[i][j-n+1]=g[i][q[head]];//以i,j-n+1开头的最小值
            }
        }
    }
    for(int j=1;j<=b-n+1;j++)
    {
        HEAD=TAIL=head=tail=Q[1]=q[1]=1;//先初始化为第一行
        for(int i=2;i<=a;i++)
        {
             while(HEAD<=TAIL&&X[Q[TAIL]][j]<=X[i][j])
               TAIL--;
            while(head<=tail&&x[q[tail]][j]>=x[i][j])
                tail--;
            TAIL++;
            tail++;
            Q[TAIL]=i;
            q[tail]=i;
            //出队操作
            //如果超过了n,则队首出队
            while(i-Q[HEAD]>=n)
                HEAD++;
            while(i-q[head]>=n)
                head++;
            if(i>=n)
            {
                Y[i-n+1][j]=X[Q[HEAD]][j];//以i-n+1,j开头的最大值
                y[i-n+1][j]=x[q[head]][j];//以i-n+1,j开头的最小值
            }
        }
    }
    int ans=0x3f3f3f3f;
    for(int i=1;i<=a-n+1;i++)
    {
        for(int j=1;j<=b-n+1;j++)
        {
            ans=min(ans,Y[i][j]-y[i][j]);
        }
    }
    cout<<ans<<endl;
    return 0;
}
           

P2569 [SCOI2010]股票交易

https://www.luogu.org/problem/P2569

参考来自这篇题解 

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int n,m,ap,bp,as,bs,ans=0,w;
int f[2002][2002],l,r,q[2001];
//f[i][j]表示第i天后拥有j张股票赚的最多钱数
//l,r,q[x]用于单调队列
int main()
{
    scanf("%d%d%d",&n,&m,&w);//n天，m最多手头的量，w隔的天数
    memset(f,128,sizeof(f));//128实际上给f数组赋的是-inf,即-2139062144
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d%d",&ap,&bp,&as,&bs);
        for(int j=0;j<=as;j++)
            f[i][j]=-1*j*ap;//第一种情况，直接赋值，
        for(int j=0;j<=m;j++)
            f[i][j]=max(f[i][j],f[i-1][j]);//转移，如果改天不买股票
        if(i<=w)//因为第3，4种情况都有i-w-1,如果i<=w,会出现负下标
            continue;
        //第3种情况，在之前的基础上买股票，f[i,j]=max(f[i,j],f[i-w-1,k]-(j-k)*api];
        //可以进一步转化为f[i,j]=max(f[i,j],f[i-w-1,k]+k*api]-j*api;
        l=1,r=0;//单调队列准备,从小转移到大，因为是买股票，j应该是越来越大
        for(int j=0;j<=m;j++)
        {
            while(l<=r&&q[l]<j-as)
                l++;//把过期的元素扔掉
            while(l<=r&&f[i-w-1][q[r]]+q[r]*ap<=f[i-w-1][j]+j*ap)//最大值在开头，递增序列
                r--;
            q[++r]=j;//更新单调队列元素
            if(l<=r)//如果单调队列里面有元素，即可以转移,因为我们要的是最大值，所以是l
                f[i][j]=max(f[i][j],f[i-w-1][q[l]]+q[l]*ap-j*ap);


        }
        //第4种情况，在之前的基础上卖股票，f[i,j]=max(f[i,j],f[i-w-1,k]+(k-j)*bpi];
        //可以进一步转化为f[i][j]=max(f[i][j],f[i-w-1,k]+k*bp)-j*bp;
        l=1,r=0;//单调队列准备，从大转移到小，因为是卖股票，j应该是越来越小
        for(int j=m;j>=0;j--)
        {
            while(l<=r&&q[l]>j+bs)
                l++;//把过期的元素扔掉
            while(l<=r&&f[i-w-1][q[r]]+q[r]*bp<=f[i-w-1][j]+j*bp)//最大值在开头，递增序列
                r--;
            q[++r]=j;
            if(l<=r)//如果单调队列里有元素，即可转移
                f[i][j]=max(f[i][j],f[i-w-1][q[l]]+q[l]*bp-j*bp);
        }
    }
    for(int i=0;i<=m;i++)
    {
        ans=max(ans,f[n][i]);
    }
    cout<<ans<<endl;
    return 0;
}
           

牛客多校第三场F planting trees

https://ac.nowcoder.com/acm/contest/883/F

 给你一个n×n的矩形，要你求出一个面积最大的矩形使得这个矩形内的最大值减最小值小于等于M

单调队列求解

   1.暴力枚举该子矩阵的上边界和下边界。

    2.用单调队列维护每一列，然后计算最大长度。

#include<bits/stdc++.h>
using namespace std;
int const ma = 1e5 + 7;
int mp[507][507], maxn[ma], minn[ma], quema[ma], quemi[ma];
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n, m;
        int ans = 1;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                scanf("%d", &mp[i][j]);
        for (int i = 1; i <= n; i++)
        {
            for (int p = 1; p <= n; p++)//在每一行都要计算
            {
                maxn[p] = 0, minn[p] = ma;
            }
            for (int k = i; k <= n; k++)
            {
                for (int p = 1; p <= n; p++)
                {
                    maxn[p] = max(maxn[p], mp[k][p]);   //找列的最大
                    minn[p] = min(minn[p], mp[k][p]);
                }
                int f1 = 1, f2 = 1, t1 = 0, t2 = 0, l = 1;//f1,f2就相当于对头，t1,t2就相当于队尾，
                for (int r = 1; r <= n; r++)//l 和 r模拟列，k与 i的差才是行
                {
                    while (f1 <= t1 && maxn[quema[t1]] < maxn[r]) t1--;            //每进入一个值后对单调队列进行排序，f1为队头，不能超过
                    while (f2 <= t2 && minn[quemi[t2]] > minn[r]) t2--;
                    quema[++t1] = r;        //进入队列
                    quemi[++t2] = r;
                    while (l <= r &&((maxn[quema[f1]] - minn[quemi[f2]]) > m))   //f2,f1的位置就是对应队列的最大和最小值
                    {
                        l++;
                        if (f1 <= t1 && quema[f1] < l)f1++;             //这里就是把对应的值弹出去,判断位置来弹数据
                        if (f2 <= t2 && quemi[f2] < l)f2++;
                    }
                    ans = max((r - l + 1) * (k - i + 1), ans);  //行*列，去找最大的矩阵
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}
           

牛客多校第八场 A All one matrix(单调栈）

题意：问有多少个全1的子矩形，且该矩形不会被另外一个全1子矩形覆盖

解法：我们预处理每个1的高度以及每一行的前缀和，枚举每一行 i，

单调栈求出每个点 j 以h[i][j]（1的高度）为高度的矩形左边界L[j]和右边界R[j]，然后枚举每个点，

如果sum[i + 1][R[j]] - sum[i + 1][L[j] - 1] != R[j] - L[j] + 1，说明这个矩形下面一排不全是1，不会被覆盖，答案++，

然后我们要去重，可能有多个点 j，他们形成的矩形是一模一样的，我们再用一个单调栈（维护单调递增的高度）去一下重，

如果栈顶元素高度等于当前点高度，说明是重复的，不用计算。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 3005;
int h[maxn][maxn], sum[maxn][maxn], q[maxn], R[maxn], L[maxn];
char s[maxn][maxn];
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%s", s[i] + 1);
        for (int j = 1; j <= m; j++)
        {
            if (s[i][j] == '1')
                h[i][j] = h[i - 1][j] + 1;
            sum[i][j] = sum[i][j - 1] + s[i][j] - '0';
        }
    }
    int ans = 0;
    for (int i = n; i; i--)
    {
        stack<int> sta;
        sta.push(m + 1);
        for (int j = m; j; j--)
        {
            while (!sta.empty() && h[i][j] <= h[i][sta.top()])
                sta.pop();
            if (sta.empty())
                R[j] = -1;
            else
                R[j] = sta.top() - 1;
            sta.push(j);
        }
        while (!sta.empty())
            sta.pop();
        sta.push(0);
        for (int j = 1; j <= m; j++)
        {
            while (!sta.empty() && h[i][j] <= h[i][sta.top()])
                sta.pop();
            if (sta.empty())
                L[j] = -1;
            else
                L[j] = sta.top() + 1;
            sta.push(j);
        }
        while (!sta.empty())
            sta.pop();
        for (int j = 1; j <= m; j++)
        {
            if (h[i][j] == 0)
            {
                while (!sta.empty())
                    sta.pop();
                continue;
            }
            while (!sta.empty() && h[i][j] < h[i][sta.top()])
                sta.pop();
            if (sta.empty() || h[i][j] != h[i][sta.top()])
            {
                int l = L[j];
                int r = R[j];
                if (sum[i +1][r] - sum[i + 1][l - 1] != r - l + 1)
                    ans++;
                sta.push(j);
            }
        }
    }
    printf("%d\n", ans);
}