题目联动：2019HDU多校-HDU6638 Snowy Smile

提供一种扫描线做法，复杂度为$O(nSlog(n))$其中S表示的是非零点的个数。

考虑按照x排序。然后枚举x作为子矩阵的左边界，依次加入后面的点作为子矩阵的由边界。

对于每个x相同的点，在线段树上维护一个长度为y的区间连续最大和(ACwing245)。把每个x相同的点加入线段树。最后求一次区间连续最大和。

也就是枚举左右边界，利用区间连续最大和“求取”上下边界。

当坐标很分散但点不多的时候，例如2000个坐标，$n^3$的DP做法将不再有效。离散化以后的扫描线做法优势将会非常明显。

但对于本题来说。由于坐标非常集中，而且当n=100的时候点数接近10000个。这个做法将退化为$O(n^3log(n))$，不如DP做法。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100 * 100 + 233;
#define ls(x) (x << 1)
#define rs(x) ((x << 1) + 1)
#define max(a, b) (a) > (b) ? (a) : (b)
struct Node{
    int l, r, lsum, rsum, sum, dat;
}t[maxn * 4];
void build(int p, int l, int r)
{
    t[p].l = l; t[p].r = r;
    if(l == r) {t[p].lsum = 0, t[p].rsum = 0, t[p].sum = 0, t[p].dat = 0; return;}
    int mid = (l + r) >> 1;
    build(ls(p), l, mid); build(rs(p), mid + 1, r);
    t[p].dat = t[p].rsum = t[p].lsum = t[p].sum = 0;
}
void update(int p, int l, int r, int v)
{
    if(l <= t[p].l && r >= t[p].r)
    {
        t[p].dat += v;
        t[p].lsum += v;
        t[p].rsum += v;
        t[p].sum += v;
        return ;
    }
    int mid = (t[p].l + t[p].r) >> 1;
    if(l <= mid) update(ls(p), l, r, v);
    if(r > mid) update(rs(p), l, r, v);
    t[p].sum = t[ls(p)].sum + t[rs(p)].sum;
    t[p].lsum = max(t[ls(p)].lsum, t[ls(p)].sum + t[rs(p)].lsum);
    t[p].rsum = max(t[rs(p)].rsum, t[rs(p)].sum + t[ls(p)].rsum);
    t[p].dat = max(max(t[ls(p)].dat, t[rs(p)].dat), t[ls(p)].rsum + t[rs(p)].lsum);
}
int ask()
{
    return t[1].dat;
}
int a[101][101];
int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            scanf("%d", &a[i][j]);
    int ans = INT_MIN;
    for(int i = 1; i <= n; i++)
    {
        build(1, 1, n);
        for(int k = i; k <= n; k++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(a[j][k])
                {
                    update(1, j, j, a[j][k]);
                }
            }
            ans = max(ans, ask());
        }
    }
    cout << ans << endl;
}