bzoj 3022 [Balkan2012]The Best Teams

题目描述

给出 $n$ 个人的年龄和水平，然后将所有人按照水平排序

有 $m$ 次询问，每次给出年龄限制 $a$ 和人数 $k$，要求选择不超过 $k$ 个人，它们的年龄均小于等于 $a$，互不相邻且水平和最大

Solution

首先不考虑年龄限制和人数，那么我们一定是能选则选，这是一个经典的贪心

然后我们发现这个贪心可以用线段树维护，那么我们将询问离线可以去掉 $a$ 的限制，$k$ 的限制我们只需要多记录几个变量然后和权值线段树求第 $k$ 小类似的做法即可

线段树维护的东西：

$f[0/1]$ 表示 $l-1$ 这个位置选或者不选，右端点的选择情况

$s[0/1]$ 表示 $l-1$ 这个位置选或者不选，整个区间的选择个数

$v[0/1]$ 表示 $l-1$ 这个位置选或者不选，整个区间的价值和

#include <iostream>
#include <algorithm>
#define maxn 300010
#define ll long long
using namespace std;

int n, m, p[maxn];

struct node {
    int opt, v, k, id;

    friend bool operator < (const node &u, const node &v) {
        if (u.k == v.k) return u.opt < v.opt;
        return u.k < v.k;
    }
} a[maxn * 2];

#define lc i << 1
#define rc i << 1 | 1
struct Seg {
    int f[2], s[2];
    ll v[2];
} T[maxn * 4], _;
inline Seg maintain(const Seg &ls, const Seg &rs) {
    Seg o;
    for (int i = 0; i < 2; ++i) {
        o.f[i] = rs.f[ls.f[i]];
        o.s[i] = ls.s[i] + rs.s[ls.f[i]];
        o.v[i] = ls.v[i] + rs.v[ls.f[i]];
    }
    return o; 
}

void build(int i, int l, int r) {
    if (l == r) return T[i] = _, void();
    int m = l + r >> 1;
    build(lc, l, m); build(rc, m + 1, r);
    T[i] = maintain(T[lc], T[rc]);
}

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

ll query(int i, int l, int r, int k, int o) {
    if (!k) return 0; 
    if (l == r) return T[i].v[o]; int m = l + r >> 1; 
    if (T[lc].s[o] >= k) return query(lc, l, m, k, o);
    else return T[lc].v[o] + query(rc, m + 1, r, k - T[lc].s[o], T[lc].f[o]); 
}

ll ans[maxn];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n; _ = { 0, 0, 0, 0, 0, 0 };
    for (int i = 1; i <= n; ++i) cin >> a[i].k >> a[i].v, a[i].opt = 0;
    for (int i = 1; i <= n; ++i) p[i] = i;
    sort(p + 1, p + n + 1, [](const int &u, const int &v) { return a[u].v > a[v].v; });
    for (int i = 1; i <= n; ++i) a[p[i]].id = i; 
    cin >> m;
    for (int i = 1; i <= m; ++i) cin >> a[i + n].k >> a[i + n].v, a[i + n].opt = 1, a[i + n].id = i;
    sort(a + 1, a + n + m + 1);
    for (int i = 1; i <= n + m; ++i) {
        if (!a[i].opt) update(1, 1, n, a[i].id, a[i].v);
        else ans[a[i].id] = query(1, 1, n, a[i].v, 0);
    }
    for (int i = 1; i <= m; ++i) cout << ans[i] << "\n"; 
    return 0;
}