悬线法学习笔记

单调栈可以解决的问题，一部分可以用悬线法解决，悬线法更容易理解，代码量差不多。

SPOJ.com - Problem HISTOGRA

找元素的左右扩展区间。如果用选线法处理的话，定义 \(L_i\) 是可扩展做区间，如果 \(a_i \le a_{L_i-1}\)，的话可以继续继承 \(L_{L_i-1}\) 这可以看成一个递归的过程，均摊复杂度线性。

int n;
void solve2() {
    vector<int> h(n + 1);
    rep(i,1,n) cin >> h[i];
    vector<int> L(n + 1), R(n + 1);
    iota(L.begin(),L.end(),0);
    iota(R.begin(),R.end(),0);
    rep(i,1,n) while(L[i] > 1 and h[i] <= h[L[i] - 1]) L[i] = L[L[i] - 1];
    dec(i,n,1) while(R[i] < n and h[i] <= h[R[i] + 1]) R[i] = R[R[i] + 1];
    ll ans = 0;
    rep(i,1,n) ans = max(ans, 1ll * h[i] * (R[i] - L[i] + 1));
    cout << ans << "\n";
}

P4147 玉蟾宫 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

最大子矩形板子题，可以发现，就是二维的悬线，需要处理出一个 \(a\) 表示一个“纵向的前缀和”表示 \(hight\)。之后跑板子就行了。

void solve()
{    
    int n,m; cin >> n >> m;
    vector<vector<int>> a(n + 1,vector<int>(m + 1));
    rep(i,1,n) rep(j,1,m) {
        char t; cin >> t;
        if(t == 'R') continue;
        a[i][j] = a[i - 1][j] + 1;
    }
    int ans = 0;
    rep(i,1,n) {
        vector<int> L(m + 1), R(m + 1);
        rep(j,1,m) L[j] = R[j] = j;
        auto &b = a[i];
        rep(j,1,m) while(L[j] > 1 and b[j] <= b[L[j] - 1]) L[j] = L[L[j] - 1];
        dec(j,m,1) while(R[j] < m and b[j] <= b[R[j] + 1]) R[j] = R[R[j] + 1];
        rep(j,1,m) ans = max(ans, (R[j] - L[j] + 1) * b[j] * 3);  
    }
    cout << ans;
}

[P1169 ZJOI2007]棋盘制作 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

求01交替的最大子矩阵，需要处理的就是悬线左右移动时的要保证01交替。

做递推时，应该判断 \(a[i][R_j] \ne a[i][R_j+1]\) 表示相邻的不同数。

while(L[j] > 1 and h[j] <= h[L[j] - 1] and a[i][R[j]] ^ a[i][R[j] + 1])
                L[j] = L[L[j] - 1];

void solve()
{    
    int n,m; cin >> n >> m;
    vector<vector<int>> a(n + 1,vector<int>(m + 1));
    rep(i,1,n) rep(j,1,m) cin >> a[i][j];
    vector<vector<int>> s(n + 1,vector<int>(m + 1));
    rep(j,1,m) s[1][j] = 1;
    rep(i,2,n) rep(j,1,m) {
        if(a[i][j] ^ a[i - 1][j]) 
            s[i][j] = s[i - 1][j] + 1;
        else s[i][j] = 1;
    }
    int ans1 = 0, ans2 = 0;
    rep(i,1,n) {
        auto &h = s[i];
        vector<int> L(m + 1),R(m + 1);
        rep(j,1,m) L[j] = R[j] = j;
        rep(j,1,m) 
            while(L[j] > 1 and h[j] <= h[L[j] - 1] and a[i][R[j]] ^ a[i][R[j] + 1])
                L[j] = L[L[j] - 1];
        dec(j,m,1) 
            while(R[j] < m and h[j] <= h[R[j] + 1] and a[i][R[j]] ^ a[i][R[j] + 1])
                R[j] = R[R[j] + 1];
        rep(j,1,m) {
            ans1 = max(ans1, min(h[j], R[j] - L[j] + 1) * min(h[j], R[j] - L[j] + 1));
            ans2 = max(ans2, h[j] * (R[j] - L[j] + 1));
        }
    }
    cout << ans1 << "\n" << ans2;
}

极大矩阵计数，看下面例题。

2022牛客国庆集训派对day6 A(极大矩阵计数) - Mxrurush - 博客园 (cnblogs.com)