2019杭电多校 Snowy Smile hdu6638 （线段树最大子段和）

题意：散落一些点，有正负价值，框一个矩形，使得矩形中的价值总和最大

题解：先把y离散化，之后x排序后依次插入点，枚举每一种不同的x坐标作为上边界，枚举下边界，线段树更新最大子段和

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<cmath> #include<queue> #include<list> #include<math.h> #include<vector> #include<stack> #include<string> #include<stdio.h>using namespace std; typedef long long LL; const int MAXN = 2e3 + 10;const int maxn=5e4 + 10;struct T{LL x,y,w;T(){}T(LL x,LL y,LL w) : x(x),y(y),w(w){} }a[MAXN];struct Segtree{int l,r;LL lx,rx,mx,sum; }st[MAXN << 2];bool cmp(T a,T b) {return a.x < b.x; } LL b[MAXN];void pushup(int o) {st[o].sum = st[o << 1].sum + st[o << 1 | 1].sum;st[o].lx = max(st[o << 1].lx,st[o << 1].sum + st[o << 1 | 1].lx);st[o].rx = max(st[o << 1 | 1].rx,st[o << 1 | 1].sum + st[o << 1].rx);st[o].mx = max(max(st[o << 1].mx,st[o << 1 | 1].mx),st[o << 1].rx + st[o << 1 | 1].lx); } void build(int o,int l,int r) {st[o].l = l; st[o].r = r;st[o].sum = st[o].mx = st[o].lx = st[o].rx = 0;if(l == r){return;}int m = (l + r) >> 1;build(o << 1, l, m);build(o << 1 | 1, m + 1, r); } void insert(int o,int x,int w) {if(st[o].l == st[o].r){st[o].sum = st[o].lx = st[o].rx = st[o].mx = st[o].mx + w;return;}int m = (st[o].l + st[o].r) >> 1;if(x <= m) insert(o << 1,x,w);else insert(o << 1 | 1,x,w);pushup(o); } int main() {int t;scanf("%d",&t);while(t--){int n;scanf("%d",&n);for(int i = 1; i <= n; i++){LL x,y,w;scanf("%lld %lld %lld",&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,st[1].mx);insert(1,a[j].y,a[j].w);}ans = max(ans,st[1].mx);}cout << ans << endl;} }

 

转载于:https://www.cnblogs.com/smallhester/p/11319701.html

总结

以上是生活随笔为你收集整理的2019杭电多校 Snowy Smile hdu6638 （线段树最大子段和）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。