2019 杭电多校第6场 HDU - 6638 Snowy Smile 线段树 最大子段和

题目链接：https://vjudge.net/problem/HDU-6638

题意：n个点，画一个矩形，使得矩形内的所有点的权值最大，求最大权值

题解：首先将坐标离散化到 O(n) 的范围内，方便后续的处理。 将所有点按照y坐标排序，枚举矩形的上边界，然后往后依次加入每行的点，这样就确定了 矩形的上下边界。线段树维护下每个点的权值，则答案即为最大连续子段和，。 时间复杂度 O(n 2 log n)。维护的时候还要记录左连续，右连续，区间和，区间连续最大值，方便在pushup的时候使用。

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2010; struct Point {int x, y, w;bool operator < (const Point &b) const {if(y != b.y) return y < b.y;else return x < b.x;} }p[N]; int n, b[N], len1, len2; struct node {int l, r;ll maxx, lm, rm, sum; }tree[N << 2]; void build(int l, int r, int cur) {tree[cur].l = l;tree[cur].r = r;tree[cur].maxx = tree[cur].lm = tree[cur].rm = tree[cur].sum = 0;if(l == r) return;int mid = (r + l) >> 1;build(l, mid, cur << 1);build(mid + 1, r, cur << 1 | 1); } void pushup(int cur) {tree[cur].maxx = max(0LL, max(tree[cur << 1].maxx, tree[cur << 1 | 1].maxx));tree[cur].maxx = max(tree[cur].maxx, max(0LL, tree[cur << 1].rm) + max(0LL, tree[cur << 1 | 1].lm));tree[cur].lm = max(0LL, max(tree[cur << 1].lm, tree[cur << 1].sum + tree[cur << 1 | 1].lm));tree[cur].rm = max(0LL, max(tree[cur << 1 | 1].rm, tree[cur << 1 | 1].sum + tree[cur << 1].rm));tree[cur].sum = tree[cur << 1].sum + tree[cur << 1 | 1].sum; } void update(int pos, int cur, int val) {if(tree[cur].l == tree[cur].r) {tree[cur].maxx += val;tree[cur].lm += val;tree[cur].rm += val;tree[cur].sum += val;return;}if(pos <= tree[cur << 1].r) update(pos, cur << 1, val);else update(pos, cur << 1 | 1, val);pushup(cur); } int main() {int T, pos;ll ans;scanf("%d", &T);while(T--) {scanf("%d", &n);len1 = len2 = 0;for(int i = 1; i <= n; i++) scanf("%d %d %d", &p[i].x, &p[i].y, &p[i].w), b[++len1] = p[i].x;sort(b + 1, b + 1 + len1);len1 = unique(b + 1, b + 1 + len1) - (b + 1);for(int i = 1; i <= n; i++) p[i].x = lower_bound(b + 1, b + 1 + len1, p[i].x) - b;for(int i = 1; i <= n; i++) b[++len2] = p[i].y;sort(b + 1, b + 1 + len2);len2 = unique(b + 1, b + 1 + len2) - (b + 1);for(int i = 1; i <= n; i++) p[i].y = lower_bound(b + 1, b + 1 + len2, p[i].y) - b;sort(p + 1, p + 1 + n); ans = 0;for(int i = 1; i <= len2; i++) {for(int j = n; j >= 1; j--) {if(p[j].y <= i) {pos = j;break;}}build(1, len1, 1);for(int j = i; j >= 1; j--) {while(pos && p[pos].y >= j) {update(p[pos].x, 1, p[pos].w);pos--;}ans = max(ans, tree[1].maxx);} } printf("%lld\n", ans);}return 0; }

 

总结

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

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