Snowy Smile （HDU - 6638，稀疏矩阵子矩阵最大和）

一.题目链接：

HDU-6638

二.题目大意：

求稀疏矩阵子矩阵最大和.

三.分析：

离散 x 坐标，枚举 x.

线段树维护区间最大子段和

将  的算法优化到了 

详见代码.

四.代码实现：

#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <bitset>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-8
#define lc k * 2
#define rc k * 2 + 1
#define pi acos(-1.0)
#define ll long long
#define ull unsigned long long
using namespace std;

const int M = (int)2e3;
const int mod = 99991;
const int inf = 0x3f3f3f3f;

struct node1
{
    int x, y, w;
}s[M + 5];
int len, y[M + 5];

struct node2
{
    ll sum, max_sum, max_prefix, max_suffix;
}tree[M * 4 + 5];

bool cmp(node1 a, node1 b)
{
    return a.x < b.x;
}

int tofind(int x)
{
    return lower_bound(y + 1, y + len + 1, x) - y;
}

void push_up(int k)
{
    tree[k].sum = tree[lc].sum + tree[rc].sum;
    tree[k].max_sum = max(max(tree[lc].max_sum, tree[rc].max_sum), tree[lc].max_suffix + tree[rc].max_prefix);
    tree[k].max_prefix = max(tree[lc].max_prefix, tree[lc].sum + tree[rc].max_prefix);
    tree[k].max_suffix = max(tree[rc].max_suffix, tree[rc].sum + tree[lc].max_suffix);
}

void update(int k, int l, int r, int pos, int v)
{
    if(l == r)
    {
        tree[k].max_prefix = tree[k].max_suffix = tree[k].max_sum = tree[k].sum += v;
        return;
    }
    int mid = (l + r) >> 1;
    if(pos <= mid)
        update(lc, l, mid, pos, v);
    else
        update(rc, mid + 1, r, pos, v);
    push_up(k);
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        len = 0;
        int n;
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d %d %d", &s[i].x, &s[i].y, &s[i].w);
            y[++len] = s[i].y;
        }
        sort(s + 1, s + n + 1, cmp), sort(y + 1, y + len + 1);
        len = unique(y + 1, y + len + 1) - (y + 1);
        ll ans = 0;
        for(int i = 1; i <= n; ++i)
        {
            if(i != 1 && s[i].x == s[i - 1].x)  continue;///一次性枚举所有 ≥ 此 x 的点.
            memset(tree, 0, sizeof(tree));
            for(int j = i; j <= n; ++j)
            {
                update(1, 1, len, tofind(s[j].y), s[j].w);
                if(j == n || s[j].x != s[j + 1].x)
                ///只有当与该 x 相等的点都加进去之后，才统计最大值.
                    ans = max(ans, tree[1].max_sum);
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}