HDU6638-Snowy Smile(线段树+最大子段和)

题目链接:HDU6638-Snowy Smile

题意:

二维坐标平面上有n个点,每个点都有相应的权值,需要画一个矩形,收益为矩形内部(包括边界上)所有权值的和,问最大收益。

题解:

首先把点按横坐标排序,然后枚举左右边界。

对于一定的左右边界内的点,标号之后用线段树维护最大字段和。

参考代码:

#include <bits/stdc++.h>
#define IL inline
using namespace std;
typedef long long ll;
const int MAXN = 2e3 + 5;
const int inf = 0x3f3f3f3f;
int T;
int n;
struct point
{
    int x, y;
    ll val;
} a[MAXN];
map<int, int> mp;
ll sum[MAXN << 2], ls[MAXN << 2], rs[MAXN << 2], ms[MAXN << 2];
IL void pushup(int rt)
{
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
    ls[rt] = max(ls[rt << 1], sum[rt << 1] + ls[rt << 1 | 1]);
    rs[rt] = max(rs[rt << 1 | 1], sum[rt << 1 | 1] + rs[rt << 1]);
    ms[rt] = max({ms[rt << 1], ms[rt << 1 | 1], rs[rt << 1] + ls[rt << 1 | 1], ls[rt], rs[rt]});
}
IL void build(int l, int r, int rt)
{
    ls[rt] = rs[rt] = ms[rt] = 0;
    sum[rt] = 0;
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    build(l, mid, rt << 1);
    build(mid + 1, r, rt << 1 | 1);
}
IL void update(int pos, ll val, int l, int r, int rt)
{
    if (l == r && l == pos)
    {
        sum[rt] += val;
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid)
        update(pos, val, l, mid, rt << 1);
    else
        update(pos, val, mid + 1, r, rt << 1 | 1);
    pushup(rt);
}
IL bool cmp(point xx, point yy)
{
    if (xx.x == yy.x)
        return xx.y < yy.y;
    return xx.x < yy.x;
}
int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &n);
        mp.clear();
        for (int i = 1; i <= n; i++)
        {
            scanf("%d%d%lld", &a[i].x, &a[i].y, &a[i].val);
            mp[a[i].y] = 0;
        }
        sort(a + 1, a + 1 + n, cmp);
        int pcnt = 0;
        for (auto &it : mp)
            it.second = pcnt++;
        ll ans = 0;
        for (int l = 1; l <= n; l++) //枚举左边界
        {
            if (l > 1 && a[l].x == a[l - 1].x) //同一左边界已经被枚举过
                continue;
            ll temp = 0;
            build(0, pcnt, 1);          //维护最大子段和
            for (int r = l; r < n; r++) //枚举右边界
            {
                update(mp[a[r].y], a[r].val, 0, pcnt, 1);
                if (a[r].x == a[r + 1].x) //保证右边界的完整。把右边界上的点全部更新后再计入答案
                    continue;
                temp = max(temp, ms[1]);
            }
            update(mp[a[n].y], a[n].val, 0, pcnt, 1);
            ans = max({ans, temp, ms[1]});
        }
        printf("%lld\n", ans);
    }
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。