传送门

题意很简单，就是求矩阵的最大子矩阵。

数据范围是坐标很多，但是点最多有2000个。100组数据。

根据x坐标排序。对y坐标进行离散化。

枚举x坐标作为左边界，再依次加入某些x相同的点，这样就确定了右边界。

用线段树维护y方向的区间连续最大和。

总体来说就是枚举左右边界，用区间连续最大和来“确定”上下边界。

联动ACWING126

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2002;
typedef long long ll;
#define ls(x) (x << 1)
#define rs(x) ((x << 1) + 1)
#define max(a, b) (a) > (b) ? (a) : (b)
struct Node{
    ll l, r, lsum, rsum, sum, dat;
}t[maxn * 4];
void build(ll p, ll l, ll 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;}
    ll 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(ll p, ll l, ll r, ll 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 ;
    }
    ll 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);
}
ll ask()
{
    return t[1].dat;
}
pair<pair<int,int> ,int > a[maxn];
set<int> st;
unordered_map<int,int> ump;
int main()
{
    int T; cin >> T;
    while(T--)
    {
        int x, y, w;
        st.clear();
        ump.clear();
        int n; scanf("%d", &n);
        for(int i = 1; i <= n; i++) 
        {
            scanf("%d%d%d", &x, &y, &w);
            a[i] = {{x, y}, w};
            st.insert(y);
        }
        int cnt = 0;
        for(auto it = st.begin(); it != st.end(); it++)
            ump[*it] = ++cnt;

        sort(a + 1, a + 1 + n);
        ll ans = LONG_LONG_MIN;
        for(int i = 1; i <= n; i++)
        {
            if(a[i].first.first == a[i - 1].first.first) continue;
            build(1, 1, cnt);
            for(int k = i; k <= n;)
            {
                int j = k;
                while(j <= n && a[j].first.first == a[k].first.first)
                {
                    int y = ump[a[j].first.second], w = a[j].second;
                    update(1, y, y, w);
                    j++;
                }
                ans = max(ans, ask());
                k = j;
            }
        }
        cout << ans << endl;
    }
}