CF1320C World of Darkraft-Battle for Azathoth

发表于2020-09-03更新于2023-09-17字数统计839阅读时长8分

World of Darkraft-Battle for Azathoth

Description

给定 n 种武器(攻击为 xix_i， 价格为 cic_i)，m 种(防御为 yjy_j，cjc_j)防具， p 个怪物(防御为 xkx_k， 攻击 yky_k， 金币 zkz_k)。

你必须选择一个武器(攻击力为 xx)和一个防具(防御为 yy)， 一个怪物 kk 能被击杀，当且仅当 x>xkx > x_k 并且 y>yky > y_k。求最大收益(可能为负)。

Solution

  • 将怪物按照防御 yky_k 排序，从小到大处理(类似扫描线)。
    1
    2
    3
    for (int i = 0, v, c; i < n; i++) //武器与怪物防御力放在一起排序
        read(v), read(c), vec.emplace_back(make_pair(v - 1, make_pair(Inf, c)));
    for(...) vec.emplace_back(make_pair(def, make_pair(atk, c)));
  • 找到最小的 jj 使得 yj>yky_j > y_k，则编号 ≥j\ge j 的所有防具获得的金币 DjD_j 都加上 zkz_k(金币初始值为 −cj-c_j)。
  • upper_bound 找到 xi>xx_i > x， 则最大获利为−ci+max⁡Dj-c_i + \max D_j。
  • 按防具下标建立线段树维护最大值, 支持区间增值即可。

注意：

  • 最大收益可能为-2e9。
  • 对pair排序以及upper_bound, 为防止临时变量第二关键值影响需将其设为Inf
    int pos = upper_bound(armor.begin(), armor.end(), make_pair(y, Inf)) - armor.begin();

Code

World of Darkraft-Battle for Azathoth
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>

constexpr int MAXN = 2e5 + 5;
constexpr int Inf = 0x7fffffff;

using namespace std;
using LL = long long;

template <typename T>
inline void read(T &x) {
    int f = 1;
    x = 0;
    char ch = getchar();
    while (!isdigit(ch)) f = (ch == '-') ? -1 : 1, ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
    x *= f;
}

struct segTree {
    segTree *Lson, *Rson;
    int l, r;
    int max, tag;
} Tree[MAXN << 1];
int tot, n, m, p, ans = -Inf;
vector<pair<int, int> > weapon, armor;
vector<pair<int, pair<int, int> > > vec;

using Node = segTree *;
#define Lson root->Lson
#define Rson root->Rson
inline void build(int L, int R, Node root) {
    root->l = L, root->r = R;
    if (L == R) {
        root->max = -armor[L].second;
        return;
    }
    int mid = (L + R) >> 1;
    Lson = &Tree[++tot], Rson = &Tree[++tot];
    build(L, mid, Lson), build(mid + 1, R, Rson);
    root->max = max(Lson->max, Rson->max);
}

inline void pushTag(Node root) {
    if (!root->tag) return;
    Lson->tag += root->tag, Lson->max += root->tag;
    Rson->tag += root->tag, Rson->max += root->tag;
    root->tag = 0;
}

inline void change(int L, int R, int val, Node root) {
    if (L <= root->l && root->r <= R) {
        root->max += val, root->tag += val;
        return;
    }
    pushTag(root);
    int mid = (root->l + root->r) >> 1;
    if (L <= mid) change(L, R, val, Lson);
    if (R > mid) change(L, R, val, Rson);
    root->max = max(Lson->max, Rson->max);
}

int main() {
    read(n), read(m), read(p);
    for (int i = 0, v, c; i < n; i++)  //武器与怪物防御力放在一起排序
        read(v), read(c), vec.emplace_back(make_pair(v - 1, make_pair(Inf, c)));
    for (int i = 0, v, c; i < m; i++)
        read(v), read(c), armor.emplace_back(make_pair(v, c));
    sort(armor.begin(), armor.end());  //防具按防御值升序排序
    build(0, m - 1, Tree);             //按防具下标建树
    for (int i = 0, def, atk, c; i < p; i++) {
        read(def), read(atk), read(c);
        vec.emplace_back(make_pair(def, make_pair(atk, c)));
    }
    sort(vec.begin(), vec.end());
    for (auto &i : vec) {
        int x = i.first, y = i.second.first, c = i.second.second;
        if (y == Inf) {  // y = inf表明这是一个武器
            ans = max(ans, -c + Tree->max);
            continue;
        }
        int pos = upper_bound(armor.begin(), armor.end(), make_pair(y, Inf)) -
                  armor.begin();
        if (pos < m) change(pos, m - 1, c, Tree);  //后缀区间增值
    }
    cout << ans << endl;
    return 0;
}