Snowy Smile

题目传送门

解题思路

先把y离散化，然后把点按照x的大小进行排序，我们枚举每一种x作为上边界，然后再枚举其对应的每一种下边界。按照这种顺序插入点，这是一个压维的操作，即在线段树中的y位置加上其w，并利用线段树来更新动态的最大子段和。

代码如下

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f

using namespace std;

typedef long long ll;

const int N = 2005;

struct T{

    ll x, y, w;

    T(){}

    T(ll x, ll y, ll w): x(x), y(y), w(w){}

}a[N];

bool cmp(const T& a, const T& b)

{

    return a.x < b.x;

}

int b[N];

struct {

    int l, r;

    ll lx, rx, mx;

    ll sum;

}tree[N << 2];

void build(int k, int l, int r)

{

    tree[k].l = l;

    tree[k].r = r;

    tree[k].sum = tree[k].lx = tree[k].rx = tree[k].mx = 0;

    if(l == r)

        return;

    int mid = (l + r) / 2;

    build(2*k, l, mid);

    build(2*k + 1, mid + 1, r);

}

void push_up(int k)

{

    tree[k].sum = tree[2*k].sum + tree[2*k+1].sum;

    tree[k].lx = max(tree[2*k].lx, tree[2*k].sum + tree[2*k+1].lx);

    tree[k].rx = max(tree[2*k+1].rx, tree[2*k+1].sum + tree[2*k].rx);

    tree[k].mx = max(max(tree[2*k].mx, tree[2*k+1].mx), tree[2*k].rx + tree[2*k+1].lx);

}

void insert(int k, int x, int w)

{

    if(tree[k].l == tree[k].r){

        tree[k].sum = tree[k].lx = tree[k].rx = tree[k].mx = tree[k].mx + w;

        return;

    }

    int mid = (tree[k].l + tree[k].r) / 2;

    if(x <= mid)

        insert(2*k, x, w);

    else

        insert(2*k+1, x, w);

    push_up(k);

}

inline ll query()

{

    return tree[1].mx;

}

int main()

{

    ios::sync_with_stdio(false);

    int t;

    cin >> t;

    while(t --){

        int n;

        cin >> n;

        for(int i = 1; i <= n; i ++){

            ll x, y, w;

            cin >> x >> y >> w;

            a[i] = T(x, y, w);

            b[i] = y;

        }

        sort(b + 1, b + n + 1);

        int k = unique(b + 1, b + n + 1) - b - 1;

        for(int i = 1; i <= n; i ++){

            int y = lower_bound(b + 1, b + k + 1, a[i].y) - b;

            a[i].y = y;

        }

        sort(a + 1, a + n + 1, cmp);

        ll ans = 0;

        for(int i = 1; i <= n; i ++){

            if(i != 1 && a[i].x == a[i - 1].x)

                continue;

            build(1, 1, k);

            for(int j = i; j <= n; j ++){

                if(j != i && a[j].x != a[j - 1].x)

                    ans = max(ans, query());

                insert(1, a[j].y, a[j].w);

            }

            ans = max(ans, query());

        }

        cout << ans << endl;

    }

    return 0;

}