Snowy Smile 线段树+扫描线 HDU多校 HDU-6638Snowy SmileSnowy Smile题意题解CODE

125 阅读 0 评论 83 点赞

我是靠谱客的博主孤独小蜜蜂，这篇文章主要介绍Snowy Smile 线段树+扫描线 HDU多校 HDU-6638Snowy SmileSnowy Smile题意题解CODE，现在分享给大家，希望可以做个参考。

Snowy Smile

Time Limit: 4000/4000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 2012 Accepted Submission(s): 640

Problem Description

There are n pirate chests buried in Byteland, labeled by 1,2,…,n. The i-th chest's location is (xi,yi), and its value is wi, wi can be negative since the pirate can add some poisonous gases into the chest. When you open the i-th pirate chest, you will get wi value.

You want to make money from these pirate chests. You can select a rectangle, the sides of which are all paralleled to the axes, and then all the chests inside it or on its border will be opened. Note that you must open all the chests within that range regardless of their values are positive or negative. But you can choose a rectangle with nothing in it to get a zero sum.

Please write a program to find the best rectangle with maximum total value.

Input

The first line of the input contains an integer T(1≤T≤100), denoting the number of test cases.

In each test case, there is one integer n(1≤n≤2000) in the first line, denoting the number of pirate chests.

For the next n lines, each line contains three integers xi,yi,wi(−109≤xi,yi,wi≤109), denoting each pirate chest.

It is guaranteed that ∑n≤10000.

Output

For each test case, print a single line containing an integer, denoting the maximum total value.

Sample Input

2 4 1 1 50 2 1 50 1 2 50 2 2 -500 2 -1 1 5 -1 1 1

Sample Output

100 6

Source

2019 Multi-University Training Contest 6

Recommend

liuyiding

题意

二维平面上有n个点，每个点有一个权值，要求划一个矩阵，使得 “矩阵中所有点的和” 最大。

题解

将坐标离散化，然后枚举矩阵的左边界和右边界，用线段树维护这左边界和右边界中间的点的最大字段和

CODE

复制代码

#include <bits/stdc++.h>
#define FOR(I,S,T) for(int I=(S);I<=(T);I++)
#define pb push_back
#define mp make_pair
#define eb emplace_back

using namespace std;
typedef long long ll;
const int maxn = 2000+3;

struct Seg{
    ll sum,vl, vr ,maxv;
}M[maxn << 2];
int x[maxn];
vector <int> v;

struct node{
    int x, y, w;
}p[maxn << 1];

bool cmp(node A, node B){
    if (A.x == B.x) return A.y < B.y;
    return A.x < B.x;
}

int getid(int x){
    return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}
int n;

void gather(int p){
    M[p].sum = M[p<<1].sum + M[p <<1 | 1].sum;
    M[p].vl = max(M[p << 1].vl ,  M[p << 1].sum + M[p << 1 | 1].vl);
    M[p].vr = max(M[p << 1 | 1].vr, M[p << 1].vr + M[p << 1 |1].sum);
    M[p].maxv = max(max(M[p << 1].maxv, M[p << 1 |1]. maxv), M[p << 1].vr + M[p << 1 |1].vl);
}

void modify(int p , int tl, int tr, int pos, int v){
    if (tl > tr) return;
    if (tl == tr && tl == pos){
        M[p].sum += v;
        M[p].vl += v;
        M[p].vr += v;
        M[p].maxv += v;
        return;
    }
    int mid = (tl + tr) / 2;
    if (mid >= pos) modify(p <<1, tl ,mid, pos, v);
    else modify(p << 1| 1, mid +1, tr, pos, v);
    gather(p);
}

int main() {
    int T;
    cin >> T;
    while (T--){
        v.clear();
        scanf("%d", &n);
        for (int i = 1; i <= n; i++){
            scanf("%lld%lld%lld", &p[i].x, &p[i].y, &p[i].w);
            x[i] = p[i].x;
            v.pb(p[i].y);
        }
        sort(x +1, x +1+n); sort(p + 1, p + 1 +n ,cmp);
        int lx = unique(x + 1, x + 1 + n) - x - 1;
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(), v.end()), v.end());

int ly = v.size();
        ll ans = 0;
        for (int i = 1; i <= lx; i++){
            int k = 1;
            while (p[k].x < x[i] && k <= n) k++;
            memset(M, 0, sizeof(M));
            for (int j = i; j <= lx; j++){
                while (p[k].x == x[j] && k <= n){
                    modify(1, 1, ly, getid(p[k].y), p[k].w);
                    k++;
                }
                ans = max(ans, M[1].maxv);
            }
        }
        cout << ans << endl;
    }

return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>
#define FOR(I,S,T) for(int I=(S);I<=(T);I++)
#define pb push_back
#define mp make_pair
#define eb emplace_back

using namespace std;
typedef long long ll;
const int maxn = 2000+3;

struct Seg{
    ll sum,vl, vr ,maxv;
}M[maxn << 2];
int x[maxn];
vector <int> v;

struct node{
    int x, y, w;
}p[maxn << 1];

bool cmp(node A, node B){
    if (A.x == B.x) return A.y < B.y;
    return A.x < B.x;
}

int getid(int x){
    return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}
int n;

void gather(int p){
    M[p].sum = M[p<<1].sum + M[p <<1 | 1].sum;
    M[p].vl = max(M[p << 1].vl ,  M[p << 1].sum + M[p << 1 | 1].vl);
    M[p].vr = max(M[p << 1 | 1].vr, M[p << 1].vr + M[p << 1 |1].sum);
    M[p].maxv = max(max(M[p << 1].maxv, M[p << 1 |1]. maxv), M[p << 1].vr + M[p << 1 |1].vl);
}

void modify(int p , int tl, int tr, int pos, int v){
    if (tl > tr) return;
    if (tl == tr && tl == pos){
        M[p].sum += v;
        M[p].vl += v;
        M[p].vr += v;
        M[p].maxv += v;
        return;
    }
    int mid = (tl + tr) / 2;
    if (mid >= pos) modify(p <<1, tl ,mid, pos, v);
    else modify(p << 1| 1, mid +1, tr, pos, v);
    gather(p);
}

int main() {
    int T;
    cin >> T;
    while (T--){
        v.clear();
        scanf("%d", &n);
        for (int i = 1; i <= n; i++){
            scanf("%lld%lld%lld", &p[i].x, &p[i].y, &p[i].w);
            x[i] = p[i].x;
            v.pb(p[i].y);
        }
        sort(x +1, x +1+n); sort(p + 1, p + 1 +n ,cmp);
        int lx = unique(x + 1, x + 1 + n) - x - 1;
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(), v.end()), v.end());

        int ly = v.size();
        ll ans = 0;
        for (int i = 1; i <= lx; i++){
            int k = 1;
            while (p[k].x < x[i] && k <= n) k++;
            memset(M, 0, sizeof(M));
            for (int j = i; j <= lx; j++){
                while (p[k].x == x[j] && k <= n){
                    modify(1, 1, ly, getid(p[k].y), p[k].w);
                    k++;
                }
                ans = max(ans, M[1].maxv);
            }
        }
        cout << ans << endl;
    }

    return 0;
}