悬线法学习笔记&总结

悬线法是一类用于解决最大子矩阵的问题的算法，其大概的代码实现和dp递推差不多？
大致算法是我们用一条线(横竖貌似都行)左右移动直到不满足约束条件或者到达边界，统计最大扩展的距离。

然后我们注意的是红色的面积更大，这样的情况也可以在红色的边界被算上，所以这大概是悬线法算法的正确性。
接下来举一些悬线法的例题，或者是思想类似于悬线法的例题来分析一下。

洛谷P1387 最大正方形
https://www.luogu.com.cn/problem/P1387
悬线法模板，只需要求三个数组l和r和up就可以。
代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=2e3+5;
int n,m,a[N][N],l[N][N],r[N][N],up[N][N],ans;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
        scanf("%d",&a[i][j]);
        if(a[i][j]==1)l[i][j]=r[i][j]=j,up[i][j]=1;
    }
    for(int i=1;i<=n;i++)for(int j=2;j<=m;j++)if(a[i][j]){
        if(a[i][j-1])l[i][j]=l[i][j-1];
    }else l[i][j]=0;
    for(int i=1;i<=n;i++)for(int j=m-1;j;j--)if(a[i][j]){
        if(a[i][j+1])r[i][j]=r[i][j+1];
    }else r[i][j]=0;
    for(int i=1;i<=n;i++)for(int j=1,x,y;j<=m;j++){
        if(i>1&&a[i][j]&&a[i-1][j])
            l[i][j]=max(l[i][j],l[i-1][j]),r[i][j]=min(r[i][j],r[i-1][j]),up[i][j]=up[i-1][j]+1;
        //printf("ij:%d %d %d %d\n",i,j,l[i][j],r[i][j]);
        x=r[i][j]-l[i][j]+1;y=min(up[i][j],x);
        ans=max(ans,y);
    }
    printf("%d\n",ans);
    return 0;
}

洛谷P2701 [USACO5.3]巨大的牛棚Big Barn
https://www.luogu.com.cn/problem/P2701
就除了输入方式不一样，其他还是和上题几乎一样的，同样是模板题。
代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e3+5;
int n,t,a[N][N],l[N][N],r[N][N],up[N][N],ans;
int main(){
    scanf("%d%d",&n,&t);
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)a[i][j]=1;
    while(t--){
        int x,y;scanf("%d%d",&x,&y);
        a[x][y]=0;
    }
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(a[i][j])l[i][j]=r[i][j]=j,up[i][j]=1;
    for(int i=1;i<=n;i++)for(int j=2;j<=n;j++)if(a[i][j]){
        if(a[i][j-1])l[i][j]=l[i][j-1];
    }else l[i][j]=0;
    for(int i=1;i<=n;i++)for(int j=n-1;j;j--)if(a[i][j]){
        if(a[i][j+1])r[i][j]=r[i][j+1];
    }else r[i][j]=0;
    for(int i=1;i<=n;i++)for(int j=1,x,y;j<=n;j++){
        if(i>1&&a[i][j]&&a[i-1][j])
            l[i][j]=max(l[i][j],l[i-1][j]),r[i][j]=min(r[i][j],r[i-1][j]),up[i][j]=up[i-1][j]+1;
        x=r[i][j]-l[i][j]+1;y=min(x,up[i][j]);
        ans=max(ans,y);
    }
    printf("%d\n",ans);
    return 0;
}

洛谷P1169 [ZJOI2007]棋盘制作
https://www.luogu.com.cn/problem/P1169
还是裸题，求一个长方形还是一样的套路，我们只需要把宽度和up的深度相乘就可以了，需要注意的是，要求01相间，我们要换一个判断的条件，只需要满足不相等就判断就可以了。
代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=2e3+5;
int n,m,a[N][N],l[N][N],r[N][N],up[N][N],ans,ans2;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
        scanf("%d",&a[i][j]);
        l[i][j]=r[i][j]=j;up[i][j]=1;
    }
    for(int i=1;i<=n;i++)for(int j=2;j<=m;j++)if(a[i][j]!=a[i][j-1])l[i][j]=l[i][j-1];
    for(int i=1;i<=n;i++)for(int j=m-1;j;j--)if(a[i][j]!=a[i][j+1])r[i][j]=r[i][j+1];
    for(int i=1;i<=n;i++)for(int j=1,x,y;j<=m;j++){
        if(i>1&&a[i][j]!=a[i-1][j])
            l[i][j]=max(l[i][j],l[i-1][j]),r[i][j]=min(r[i][j],r[i-1][j]),up[i][j]=up[i-1][j]+1;
        x=r[i][j]-l[i][j]+1;y=min(x,up[i][j]);
        ans=max(ans,y*y);ans2=max(ans2,x*up[i][j]);
    }
    printf("%d\n%d\n",ans,ans2);
    return 0;
}

洛谷P4147 玉蟾宫 SP277 CTGAME - City Game UVA1330 City Game
https://www.luogu.com.cn/problem/P4147
https://www.luogu.com.cn/problem/SP277
https://www.luogu.com.cn/problem/UVA1330
这是一个三倍经验，还是一样的问题，单独求一个长方形就可以了！
代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e3+5;
int n,m,a[N][N],l[N][N],r[N][N],up[N][N],ans;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
        char opt[5];scanf("%s",opt);
        if(opt[0]=='F')a[i][j]=1;else a[i][j]=0;
    }
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(a[i][j])l[i][j]=r[i][j]=j,up[i][j]=1;
    for(int i=1;i<=n;i++)for(int j=2;j<=m;j++)if(a[i][j]){
        if(a[i][j-1])l[i][j]=l[i][j-1];
    }else l[i][j]=0;
    for(int i=1;i<=n;i++)for(int j=m-1;j;j--)if(a[i][j]){
        if(a[i][j+1])r[i][j]=r[i][j+1];
    }else r[i][j]=0;
    for(int i=1;i<=n;i++)for(int j=1,x,y;j<=m;j++){
        if(i>1&&a[i-1][j]&&a[i][j])
            l[i][j]=max(l[i][j],l[i-1][j]),r[i][j]=min(r[i][j],r[i-1][j]),up[i][j]=up[i-1][j]+1;
        ans=max(ans,(r[i][j]-l[i][j]+1)*up[i][j]);
    }
    printf("%d\n",ans*3);
    return 0;
}

洛谷P3474 [POI2008]KUP-Plot purchase
https://www.luogu.com.cn/problem/P3474
这题不是模板题，也是运用了悬线法。
首先我们考虑如果一个数大于2k，这个数肯定没有用，我们不考虑它。
如果小于等于2k，并且大于等于k，那么我们显然已经找到了答案。
然后我们剩下只需要考虑小于k的情况，我们其他的数都标记为不能选，然后我们考虑对于一个全是小于k的选法。
我们考虑如果答案有解，那么选择一个子矩形的sum如果大于等于2k。
因为我们可以把这个子矩形一行一行删，一定可以找到答案（前提条件是我们选的数都是小于k的）
这题主要考虑以上的思路，如果这个想出来了，下面就很好做了。
注意有点小细节，如果删到只剩下一行，我们就一个数一个数删。
因此我们可以成功的把这个转化为悬线法解决，只需要维护一个二维前缀和就可以了。
代码:

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=2e3+5;
int k,n,a[N][N],l[N][N],r[N][N],up[N][N],X,Y,X2,Y2;
LL s[N][N];bool fl[N][N],fl2;
LL calc(int x,int y,int x2,int y2){return s[x2][y2]-s[x-1][y2]-s[x2][y-1]+s[x-1][y-1];}
int main(){
    scanf("%d%d",&k,&n);
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&a[i][j]),s[i][j]=s[i-1][j]+s[i][j-1]+(LL)a[i][j]-s[i-1][j-1];
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(a[i][j]<=(k<<1)){
        if(a[i][j]>=k){printf("%d %d %d %d\n",j,i,j,i);return 0;}
        fl[i][j]=true;l[i][j]=r[i][j]=j;up[i][j]=1;
    }
    for(int i=1;i<=n;i++)for(int j=2;j<=n;j++)if(fl[i][j]&&fl[i][j-1])l[i][j]=l[i][j-1];
    for(int i=1;i<=n;i++)for(int j=n-1;j;j--)if(fl[i][j]&&fl[i][j+1])r[i][j]=r[i][j+1];
    for(int i=1;i<=n;i++)for(int j=1,x,y,x2,y2;j<=n;j++)if(fl[i][j]){
        if(i>1&&fl[i-1][j])
            up[i][j]=up[i-1][j]+1,l[i][j]=max(l[i][j],l[i-1][j]),r[i][j]=min(r[i][j],r[i-1][j]);
        x=i-up[i][j]+1;y=l[i][j];x2=i;y2=r[i][j];
        LL now=calc(x,y,x2,y2);
        if(now>=k&&now<=(k<<1)){printf("%d %d %d %d\n",y,x,y2,x2);return 0;}
        if(now>=(k<<1))X=x,Y=y,X2=x2,Y2=y2,fl2=true;
    }
    if(!fl2){puts("NIE");return 0;}
    while(calc(X,Y,X2,Y2)>=(k<<1))if(X<X2){if(calc(X,Y,X2-1,Y2)<k)X=X2;else X2--;}else Y2--;
    printf("%d %d %d %d\n",Y,X,Y2,X2);
    return 0;
}

洛谷P3117 [USACO15JAN]Cow Rectangles G
https://www.luogu.com.cn/problem/P3117
首先考虑第一问，如果单纯只有第一问很好解决，就是模板悬线法
但是如果有第二问，其实我们可以再花O(n)的时间把它求出它的最优面积。
然后是O(n^3)，我们坐标离散化，然后可以通过此题。
这是一个变形，我们可以利用悬线法已知的范围再求一个最优解。
代码：

#include<bits/stdc++.h>
#define LL long long
#define pii pair<int,int>
using namespace std;
const int N=1e3+5,Inf=1e9;
struct node{int x,y,type;}a[N];
int t,l1,l2,c[N],d[N],mp[N][N],l[N][N],r[N][N],up[N][N];pii ans;
pii calc(int x,int y,int x2,int y2){
    int X=Inf,Y=Inf,X2=0,Y2=0,res=0;
    for(int i=1;i<=t;i++)if(a[i].x>=x&&a[i].x<=x2&&a[i].y>=y&&a[i].y<=y2)
        res++,X=min(X,c[a[i].x]),Y=min(Y,d[a[i].y]),X2=max(X2,c[a[i].x]),Y2=max(Y2,d[a[i].y]);
    return pii(res,(X2-X)*(Y2-Y));
}
void update(pii &x,pii y){if(y.first>x.first)x=y;else if(y.first==x.first)x.second=min(x.second,y.second);}
int main(){
    scanf("%d",&t);
    for(int i=1,x,y;i<=t;i++){
        scanf("%d%d",&a[i].x,&a[i].y);
        char str[5];scanf("%s",str);
        if(str[0]=='H')a[i].type=1;else a[i].type=2;
        c[++l1]=a[i].x;d[++l2]=a[i].y;
    }
    sort(c+1,c+l1+1);l1=unique(c+1,c+l1+1)-c-1;
    sort(d+1,d+l2+1);l2=unique(d+1,d+l2+1)-d-1;
    for(int i=1;i<=t;i++)a[i].x=lower_bound(c+1,c+l1+1,a[i].x)-c,a[i].y=lower_bound(d+1,d+l2+1,a[i].y)-d;
    for(int i=1;i<=t;i++)mp[a[i].x][a[i].y]=a[i].type;
    for(int i=1;i<=l1;i++)for(int j=1;j<=l2;j++)if(mp[i][j]!=2)l[i][j]=r[i][j]=j,up[i][j]=1;
    for(int i=1;i<=l1;i++)for(int j=2;j<=l2;j++)if(mp[i][j]!=2&&mp[i][j-1]!=2)l[i][j]=l[i][j-1];
    for(int i=1;i<=l1;i++)for(int j=l2-1;j;j--)if(mp[i][j]!=2&&mp[i][j+1]!=2)r[i][j]=r[i][j+1];
    for(int i=1;i<=l1;i++)for(int j=1,x,y,x2,y2;j<=l2;j++)if(mp[i][j]!=2){
        if(i>1&&mp[i-1][j]!=2)
            up[i][j]=up[i-1][j]+1,l[i][j]=max(l[i][j],l[i-1][j]),r[i][j]=min(r[i][j],r[i-1][j]);
        x=i-up[i][j]+1;y=l[i][j];x2=i;y2=r[i][j];
        pii now=calc(x,y,x2,y2);update(ans,now);
    }
    printf("%d\n%d\n",ans.first,ans.second);
    return 0;
}

接下来放两道不是悬线法，但是思路有助于我们更好理解悬线法的，或是题型类似的。
https://www.luogu.com.cn/problem/P1578
洛谷P1578 奶牛浴场
我们对于每个点都扫一下，考虑它在边界的情况，最后单独特判一下大家都是另外的方向在边界的可能性，就是一方面边界没有点的情况。
为什么要提到这道题呢？是因为这道题和我们悬线法的算法本质比较相同，就是我们算的不一定是最优解，但是最优解一定会在某个边界被算过。
代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=5e4+5;
struct node{int x,y;}a[N];
bool cmp(node a,node b){return a.x<b.x;}
bool cmp2(node a,node b){return a.y<b.y;}
int r,c,n,ans;
int main(){
    scanf("%d%d%d",&r,&c,&n);
    for(int i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y);
    a[++n]=(node){0,c};a[++n]=(node){0,0};a[++n]=(node){r,c};a[++n]=(node){r,0};
    sort(a+1,a+n+1,cmp);
    for(int i=1,up,dw;i<=n;i++){
        up=0;dw=c;
        for(int j=i+1;j<=n;j++){
            if(a[j].x==a[i].x)continue;
            ans=max(ans,(a[j].x-a[i].x)*(dw-up));
            if(a[i].y==a[j].y)break;
            if(a[j].y>a[i].y)dw=min(dw,a[j].y);else up=max(up,a[j].y);
        }
        up=0;dw=c;
        for(int j=i-1;j;j--){
            if(a[j].x==a[i].x)continue;
            ans=max(ans,(a[i].x-a[j].x)*(dw-up));
            if(a[i].y==a[j].y)break;
            if(a[j].y>a[i].y)dw=min(dw,a[j].y);else up=max(up,a[j].y);
        }
    }
    sort(a+1,a+n+1,cmp2);
    for(int i=1;i<n;i++)ans=max(ans,(a[i+1].y-a[i].y)*r);
    printf("%d\n",ans);
    return 0;
}

洛谷P3331 [ZJOI2011]礼物
https://www.luogu.com.cn/problem/P3331
这题是一个三维的问题，我们好像不能使用悬线法解决，但是我们可以利用悬线法引出的思路来解决问题。
先考虑二维的问题，我们考虑一个点假设它是左下角，然后我们看它能扩展到的最远的右上角是哪个？我们把正方形放在这个二维问题上解决，然后把b放在高度上，发现这个问题可以二分加上二维前缀和解决，但是我们发现相邻的边长不会相差1，因此我们利用这个减量来求一下就好了，就非常类似于suffix array的height数组的求法。
于是我们把这个二维问题转化到三维问题，我们用考虑一个带有高度的问题，我们只需要枚举某个高度的取的边长，然后这个高度我们考虑能取到多少，考虑因为一个区间有个min，我们一定会被算过，同理我们最优解有个左上角，我们肯定也会被算过，因此我们的最优解一定在我们考虑的范围内。我们就可以得到答案。
但是我们最后发现我们需要转三个方向分别求一下取个最优值就可以了！
这题的思路和上题还是差不多，顺便引申一下不能用悬线法，但是题型类似的题目怎么做？
还有一个比较巧妙的思路，因为这题有个aab，有个正方形，我们要想办法把好做的，或者说条件类似的放在我们自己擅长做的地方解决，也就是这道题我们放在二维上解决正方形，然后是一个解题的好办法。
代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=155;
int a[N][N][N],b[N][N][N],s[N][N],len[N][N][N],st[N],L[N],R[N],ans;char str[N];
bool check(int x,int y,int x2,int y2){return s[x2][y2]-s[x-1][y2]-s[x2][y-1]+s[x-1][y-1]==(x2-x+1)*(x2-x+1);}
void solve(int p,int q,int r){
    for(int k=1,now;k<=r;k++){
        for(int i=1;i<=p;i++)for(int j=1;j<=q;j++)
            s[i][j]=s[i-1][j]+s[i][j-1]+a[i][j][k]-s[i-1][j-1];
        now=0;
        for(int i=1;i<=p;i++)for(int j=1;j<=q;j++){
            while(i+now<=p&&j+now<=q&&check(i,j,i+now,j+now))now++;
            len[i][j][k]=now;if(now>0)now--;
        }
    }
    for(int i=1;i<=p;i++)for(int j=1,tp;j<=q;j++){
        tp=0;
        for(int k=1;k<=r;k++){
            while(tp&&len[i][j][st[tp]]>=len[i][j][k])tp--;
            if(tp)L[k]=st[tp]+1;else L[k]=1;
            st[++tp]=k;
        }
        tp=0;
        for(int k=r;k;k--){
            while(tp&&len[i][j][st[tp]]>=len[i][j][k])tp--;
            if(tp)R[k]=st[tp]-1;else R[k]=r;
            st[++tp]=k;
        }
        for(int k=1;k<=r;k++)ans=max(ans,len[i][j][k]*(R[k]-L[k]+1));
    }
}
int main(){
    int p,q,r;scanf("%d%d%d",&q,&p,&r);
    for(int i=1;i<=p;i++)for(int j=1;j<=q;j++){
        scanf("%s",str+1);
        for(int k=1;k<=r;k++)b[i][j][k]=str[k]=='N';
    }
    memcpy(a,b,sizeof(a));
    solve(p,q,r);
    for(int i=1;i<=p;i++)for(int j=1;j<=r;j++)for(int k=1;k<=q;k++)a[i][j][k]=b[i][k][j];
    solve(p,r,q);
    for(int i=1;i<=q;i++)for(int j=1;j<=r;j++)for(int k=1;k<=p;k++)a[i][j][k]=b[k][i][j];
    solve(q,r,p);
    printf("%d\n",ans<<2);
    return 0;
}

总结一下：
悬线法总归大部分都是模板题吧？没有什么新花样
我们就需要考虑两类题型：
一种是我们考虑推出特别号的性质然后转化有悬线法解决
还有一种就是我们通过悬线法求出的信息再来干一些其他的事情。
还有我们可以用一些扫描线单调栈等做法来替代悬线法，以及做一些悬线法类似的题目，需要掌握。