The 16th Heilongjiang Provincial Collegiate Programming Contest L Labi-Ribi

题目描述

http://codeforces.com/gym/103107/problem/L

简要题意：现在有 $n$ 个怪兽，第 $i$ 个怪兽有一个等级限制 $h_i$，只有等级大于等于 $h_i$ 才能杀死第 $i$ 个怪兽。现在还有一个限制，就是每一回合只能杀死一个怪兽，同时每个怪兽还有两个属性 $a_i$ 和 $b_i$，杀死怪兽 $i$ 之后其它怪兽的 $h$ 会增加 $a_i$，而你的等级会增加 $b_i$。现在还有 $q$ 个询问，每次增加一个怪兽，求目前为止你所需要的最低的初始等级杀死所有怪兽

$n\le 10^5,q\le 1000$

Solution

首先我们将 $a$ 转换为你的等级降低 $a$，为了方便，下文我们令 $c_i$ 表示杀死第 $i$ 个怪兽后增加的等级

我们先不考虑动态添加怪兽，对于现在的这些怪兽，贪心的打这些怪兽，对于 $c\ge 0$ 的怪兽，我们肯定是按照 $h$ 递增来打，对于 $c<0$，这就是一个经典的贪心，我们按照 $h+c$ 递减来打

排好序之后，答案就是 $max_{i=1}^n\lbrace h-pre_{i-1}\rbrace $，其中 $pre_{i}$ 表示前 $i$ 个怪兽的 $c$ 的和

对于动态添加，我们考虑离线添加怪物确定每个怪兽添加进来的位置，然后用线段树动态维护即可

时间复杂度 $O(n\log q)$

#include <iostream>
#include <algorithm>
#define maxn 110010
#define ll long long
#define INF 100000000000000000
using namespace std;

inline bool sig(ll v) { return v >= 0; } 

int n, m, p[maxn];

struct node {
    ll h, c;
    int k;
} a[maxn];

#define lc i << 1
#define rc i << 1 | 1
struct Seg {
    ll v, max, add;
} T[maxn * 4];
inline void maintain(int i) {
    T[i].v = T[lc].v + T[rc].v;
    T[i].max = max(T[lc].max, T[rc].max);
}

void build(int i, int l, int r) {
    if (l == r) return T[i].v = T[i].add = 0, T[i].max = -INF, void();
    int m = l + r >> 1;
    build(lc, l, m); build(rc, m + 1, r);
    maintain(i);
}

inline void Update(int i, ll add) {
    T[i].max += add;
    T[i].add += add;
}

inline void pushdown(int i) {
    ll &add = T[i].add; if (!add) return ;
    Update(lc, add); Update(rc, add);
    add = 0;
}

void update(int i, int l, int r, int k, ll h, ll c) {
    if (l == r) return T[i].v = c, T[i].max = h, void();
    int m = l + r >> 1; pushdown(i);
    if (k <= m) update(lc, l, m, k, h, c);
    else update(rc, m + 1, r, k, h, c);
    maintain(i);
}

void update(int i, int l, int r, int L, int R, ll v) {
    if (l > R || r < L) return ;
    if (L <= l && r <= R) return Update(i, v);
    int m = l + r >> 1; pushdown(i);
    update(lc, l, m, L, R, v); update(rc, m + 1, r, L, R, v);
    maintain(i);
}

ll query(int i, int l, int r, int L, int R) {
    if (l > R || r < L) return 0;
    if (L <= l && r <= R) return T[i].v;
    int m = l + r >> 1; pushdown(i);
    return query(lc, l, m, L, R) + query(rc, m + 1, r, L, R);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i].h;
    for (int i = 1, x, y; i <= n; ++i) cin >> x >> y, a[i].c = y - x;
    cin >> m;
    for (int i = 1; i <= m; ++i) {
        int x, y, z; cin >> z >> x >> y;
        a[i + n] = { z, y - x };
    }
    for (int i = 1; i <= n + m; ++i) p[i] = i;
    sort(p + 1, p + n + m + 1, [](const int &u, const int &v) {
            int s = sig(a[u].c), t = sig(a[v].c);
            if (s != t) return s > t;
            if (s > 0) return a[u].h < a[v].h; 
            else return a[u].h + a[u].c > a[v].h + a[v].c;
        });
    for (int i = 1; i <= n + m; ++i) a[p[i]].k = i;
    build(1, 1, n + m);
    for (int i = 1; i <= n; ++i) {
        update(1, 1, n + m, a[i].k, a[i].h - query(1, 1, n + m, 1, a[i].k - 1), a[i].c);
        update(1, 1, n + m, a[i].k + 1, n + m, -a[i].c);
    } cout << T[1].max << "\n";
    for (int i = n + 1; i <= n + m; ++i) {
        update(1, 1, n + m, a[i].k, a[i].h - query(1, 1, n + m, 1, a[i].k - 1), a[i].c);
        update(1, 1, n + m, a[i].k + 1, n + m, -a[i].c);
        cout << T[1].max << "\n";
    } 
    return 0; 
}