最大子矩阵整理

先上国家队dalao的博客：

最大子矩阵算法论文

算法一是以障碍物来判定极大子矩阵，即四边都有障碍物阻挡就是极大子矩阵。先将障碍物按升序排序，遍历每一个点并找到以这个点为左边界的极大子矩阵，复杂度O（s^2）

算法二是悬线法，复杂度O（nm），常数略大。每条悬线向左和向右能到达的最远的点之间距离×悬线长度即以这条悬线下端点为下边界的极大子矩阵。

三道例题：

一、玉蟾宫（题目链接：蛤）

 

此题数据较水， 前缀和暴力O(n^3)的算法加O2也能过

二、奶牛浴场（题目链接：点击打开链接）

矩阵边长很大，但是障碍物较少，所以可以用算法一

三、big barn（题目链接：点击打开链接）

障碍物很多，但是矩阵边长比较短，所以算法二跑得快

 

对算法的备注：

实际上那个博客里的算法有一丢丢疏漏，在奶牛浴场的题解里有提到。

算法一需要把左边界的所有点都加进障碍物集合内，不然顶着左右边界而不碰上下界的矩形扫不到

在从左到右扫完一遍之后还需要把顶着左右边界的极大子矩形扫一遍。即按纵坐标排序再算两个障碍物中夹的那个矩形（感谢tiandong123的纠正）

算法二貌似没什么问题，贴个big barn的代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1010;
int n, m, l[N][N], r[N][N], h[N][N], ans;
bool a[N][N];

int MAX(int x, int y){return x > y ? x : y;}
int MIN(int x, int y){return x < y ? x : y;}

int main()
{
    scanf("%d%d", &n, &m);
    memset(a, 0, sizeof(a));
    for (int i = 1; i <= m; i++){
        int x, y;
        scanf("%d%d", &x, &y);
        a[x][y] = 1;
    }
    for (int i = 0; i <= n; i++){
        int t = 0;
        for (int j = 1; j <= n; j++){
            if (a[i][j])
                l[i][j] = 0, t = j;
            else
                l[i][j] = t;
        }
        t = n+1;
        for (int j = n; j >= 1; j--){
            if (a[i][j])
                r[i][j] = n+1, t = j;
            else
                r[i][j] = t;
        }
    }
    memset(h, 0, sizeof(h));
    ans = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (!a[i][j]){
                h[i][j] = h[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]);
                ans = MAX(ans, MIN(h[i][j], r[i][j]-l[i][j]-1));
            }
    //printf("%d %d %d\n", h[745][6], l[745][6], r[745][6]);
    printf("%d", ans);
    return 0;
}

 

 

还有四个算法

        针对的是这样的输入方式：

 

        输入格式：

        第一行输入一个整数n (1≤n≤10^5)

        第二行输入n个整数表示每个矩形的高度h。 (1≤h≤10^9)

 

        输出格式：

        输出最大子矩形的面积

一、单调栈

维护一个严格单调递增的单调栈，每次插入一个元素位置为z，如果有栈顶元素（位置x，高度hx，弹出后的栈顶元素位置y，高度hy）被pop掉，就可以得到面积为(z-y)*hx。

因为在[y+1, z-1]区间内所有元素高度均不大于hy。先看x左边，如果存在比hx小的高度，那么那个元素必定在栈内，即y元素。再看右边，如果右边有高度小于hx的元素，那么x一定在之前被pop了。故可知在[y+1, z-1]区间内所有元素高度均不大于hy

贴代码：

#include<cstdio>
#include<iostream>
#include<cstring>
#define ll long long
using namespace std;
const ll N = 100010;
ll n, a[N];
ll hp[N], t, ans;

ll MAX(ll x, ll y){return x>y?x:y;}

int main()
{
    scanf("%lld", &n);
    for (ll i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    a[0] = -2;
    a[++n] = -1;
    hp[1] = 0;
    t = 1; ans = 0;
    for (ll i = 1; i <= n; i++){
        while (a[i] <= a[hp[t]]){
            ans = MAX(ans, a[hp[t]]*(i-hp[t-1]-1));
            t--;
        }
        hp[++t] = i;
    }
    printf("%lld", ans);
    return 0;
}

 

二、接近暴力的算法

 

left[i]存以i为右端点的矩阵的最左端点，以下为求left数组的方法，复杂度O(n)

left[i] = i;
while (left[i]-1 >= 0 && value[left[i-1]] >= value[left[i]])
    left[i] = left[left[i]-1];

 

三、RMQ+递归

 

对于一个[l, r]区间，最小值将它两边的元素隔开，两边无法联系，于是可以递归求解

void deal(int l, int r){
    if (r < l) return;
    int m = range_min(l, r);
    ans = max(ans, m*(r-l+1));
    deal(l, m-1);
    deal(m+1, r);
}

 

四、笛卡尔树

 

首先学习一波笛卡尔树：笛卡尔树是一棵二叉树，树的每个节点有两个值，一个为index，一个为value。光看index的话，笛卡尔树是一棵二叉搜索树，每个节点的左子树的index都比它小，右子树都比它大；光看value的话，笛卡尔树有点类似堆，根节点的value是最小（或者最大）的，每个节点的value都比它的子树要小（或者大）。 它可以处理范围最值查询、范围top k查询（range top k queries）等问题。 

简而言之，就是一棵笛卡尔树需要同时满足堆的性质和中序遍历等于原序列的性质

所以对于这个问题，只需要建一棵对于每一棵子树，求出size[i]×value[i]，取最大值就好了

贴个代码吧：

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const ll N = 100010;
ll n, h[N];
ll fa[N], ls[N], rs[N], sz[N], root;
ll ans;

ll MAX(ll x, ll y){return x>y?x:y;}

void DFS(int u)
{
    sz[u] = 1;
    if (ls[u] != 0) DFS(ls[u]), sz[u] += sz[ls[u]];
    if (rs[u] != 0) DFS(rs[u]), sz[u] += sz[rs[u]];
    ans = MAX(ans, sz[u]*h[u]);
}

int main()
{
    scanf("%lld", &n);
    for (ll i = 1; i <= n; i++)
        scanf("%lld", &h[i]);
    memset(fa, 0, sizeof(fa));
    memset(ls, 0, sizeof(ls));
    memset(rs, 0, sizeof(rs));
    h[0] = -1;  //把0设置成根节点的根节点，保证从下往上搜不会爆炸
    root = 1;
    fa[1] = 0; rs[0] = 1;
    for (int i = 2; i <= n; i++){//其实对于笛卡尔树最难的还是建树
        int j = i-1;
        while (h[j] > h[i]) //从它的前一个数开始，找到value小于它的第一个节点
            j = fa[j];
        if (j == 0) root = i;//i成为j的右儿子，j原来的右儿子（如果有的话）就变成i的左二子
        fa[i] = j;
        ls[i] = rs[j];
        fa[rs[j]] = i;
        rs[j] = i;
    }
    ans = 0;
    DFS(root);//dfs一遍出解
    printf("%lld", ans);
    return 0;
}