2019牛客2 Second Large Rectangle

题意求01矩阵第二大1矩阵的面积

真实被教育，求二大的题一般都很贱，求一大的值完全就是板子题，随便上网找找就行我这说说二大的要点。
首先错误的地方就是单调栈进去的都是当前最优的结果，所以我们会有一个hack的数据
1 4
1 1 1 1
答案显然是3但是我们会得到0…因为我们记录的都是当前最优最大的面积的矩形….
解决方法多加入一些长减一或者宽减一之类的矩形
然后就是寻找的时候好多bug,复杂的实现我就不说了,简易的实现就是把第一大面积第二大面积算出来然后再单调栈遍历一遍这个地方因为我们的复杂度大约n^2 1e6多点常数无所谓然后就是看看不重复的矩形的最大的面积是否会有多于一个等于最大值的有就直接输出最大值否则输出二大值即可.
矩形判重直接用左上角右下角坐标或者是i*m+j之类的判别
代码

#include <bits/stdc++.h>
using namespace std;
long long st[1005],a[1005][1005],h[1005][1005],l[1005],r[1005],p,q;
set<int> s;
map<long long,map<long long,long long>> bk;
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        char x;
        cin>>x;
        a[i][j]=x-'0';
    }
    for(int i=1;i<=m;i++)
    for(int j=1;j<=n;j++)
    if(a[j][i]==1)
    h[j][i]=h[j-1][i]+1;
    for(int i=1;i<=n;i++)
    {
        p=0;
        for(int j=1;j<=m;j++)
        {
            while(p&&h[i][st[p]]>=h[i][j])
            p--;
            if(p)
            l[j]=st[p];
            else
            l[j]=0;
            st[++p]=j;
        }
        p=0;
        for(int j=m;j;j--)
        {
            while(p&&h[i][st[p]]>=h[i][j])
            p--;
            if(p)
            r[j]=st[p];
            else
            r[j]=m+1;
            st[++p]=j;
        }
        for(int j=1;j<=m;j++)
        {
            s.insert((r[j]-l[j]-1)*h[i][j]);
            s.insert((r[j]-l[j]-2)*h[i][j]);
            s.insert((r[j]-l[j]-1)*(h[i][j]-1));
        }
    }
    auto it=s.end();
    int m1=*(--it);
    int m2=*(--it);
    int num__ = 0;
    for(int i=1;i<=n;i++)
    {
        p=0;
        for(int j=1;j<=m;j++)
        {
            while(p&&h[i][st[p]]>=h[i][j])
            p--;
            if(p)
            l[j]=st[p];
            else
            l[j]=0;
            st[++p]=j;
        }
        p=0;
        for(int j=m;j;j--)
        {
            while(p&&h[i][st[p]]>=h[i][j])
            p--;
            if(p)
            r[j]=st[p];
            else
            r[j]=m+1;
            st[++p]=j;
        }

        for(int j=1;j<=m;j++)
        {
            int now=(r[j]-l[j]-1)*h[i][j];
            if(now==m1&&(!bk[(i-h[i][j])*m+(l[j]+1)][(i-1)*m+(r[j]-1)]))
            {
                num__++;
                bk[(i-h[i][j])*m+(l[j]+1)][(i-1)*m+(r[j]-1)]=1;
            }
            if(num__>1)
            return printf("%d",m1),0;
        }
    }
    printf("%d",m2);
}