HDU多校第六场 1005 Snowy Smile —— 线段树维护最大子段和

本文主要是介绍HDU多校第六场 1005 Snowy Smile —— 线段树维护最大子段和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：点我啊╭(╯^╰)╮

题目大意：

    二维平面上有 $n$ 个点，权值有正有负
    选取一个正方形，里面的点全选
    求最大点值和

解题思路：

    坐标离散化之后枚举上下界
    枚举的时候就将那一行的点 $update$ 到线段树里
    然后维护最大字段和即可
    还是很好写的。。。
    那么问题又来了：线段树前加inline，是不是就变成了非递归呢？

核心：线段树维护最大子段和

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
const int maxn = 2e4 + 5;
int cas, n;
struct node{int x, y, w, lsy;
} a[maxn];
vector <int> vx, vy;
vector <node> X[maxn];
ll tl[maxn<<1], tr[maxn<<1];
ll t[maxn<<1], T[maxn<<1];inline void pushup(int rt){tl[rt] = max(tl[rt<<1], t[rt<<1] + tl[rt<<1|1]);tr[rt] = max(tr[rt<<1|1], tr[rt<<1] + t[rt<<1|1]);t[rt] = t[rt<<1] + t[rt<<1|1];T[rt] = max(max(T[rt<<1], T[rt<<1|1]), tr[rt<<1] + tl[rt<<1|1]);
} inline void build(int l, int r, int rt){tl[rt] = tr[rt] = t[rt] = T[rt] = 0;if(l == r) return;int m = l + r >> 1;build(l, m, rt<<1);build(m+1, r, rt<<1|1);
}inline void update(int l, int r, int rt, int p, int w){if(l>p || r<p) return;if(l == r){tl[rt] += w, tr[rt] += w;t[rt] += w, T[rt] += w;return;}int m = l + r >> 1;update(l, m, rt<<1, p, w);update(m+1, r, rt<<1|1, p, w);pushup(rt);
}int main() {scanf("%d", &cas);while(cas--){scanf("%d", &n);vx.clear(), vy.clear();for(int i=0; i<=n; i++) X[i].clear();for(int i=1; i<=n; i++){int x, y, w;scanf("%d%d%d", &x, &y, &w);a[i].x = x, a[i].y = y, a[i].w = w;vx.push_back(x), vy.push_back(y);}sort(vx.begin(), vx.end());sort(vy.begin(), vy.end());vx.erase(unique(vx.begin(), vx.end()), vx.end());vy.erase(unique(vy.begin(), vy.end()), vy.end());for(int i=1; i<=n; i++) {int p = lower_bound(vx.begin(), vx.end(), a[i].x) - vx.begin();a[i].lsy = lower_bound(vy.begin(), vy.end(), a[i].y) - vy.begin();X[p].push_back(a[i]);}int N = vx.size();ll ans = 0;for(int up=0; up<N; up++){build(1, n, 1);for(int dw=up; dw<N; dw++){for(int i=0; i<X[dw].size(); i++)update(1, n, 1, X[dw][i].lsy+1, X[dw][i].w);ans = max(ans, T[1]);}}printf("%lld\n", ans);} 
}

这篇关于HDU多校第六场 1005 Snowy Smile —— 线段树维护最大子段和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---