bzoj 3022 [balkan oi 2012] the best team solution 题解

简单线段树

给定 $n$ 个球员, 第 $i$ 个球员的年龄为 $a_i$ , 水平为 $s_i$ , 没有任何两人水平相同

将这些球员按水平排序,对于一次比赛,你需要选择若干个球员去比赛,但不能同时选择两个水平相邻的球员。

$m$ 次询问,每次给定 $a$ 和 $k$,表示要在年龄不超过 $a$ 的球员中选择不超过 $k$ 个球员,请计算 $mathrm{skill}$ 和的最大值

$n, m leq 3 * 10 ^ 5, a_i, s_i leq 10^9$

题解

考虑对于年龄排序就可以去掉年龄的限制,然后肯定是贪心的从大到小取。

考虑线段树,为了解决不相邻,我们维护 $g(p, 0), g(p,1)$ 表示对应区间右端点 $r + 1$ 不取或取的时候 $l$ 取不取, 这样$g(p, o) = g(mathrm{lc_p}, g(mathrm{rc_p}, o))$, 即上传了 $r + 1$ 的选取信息,且解决了中点处不相邻

那么我们对应的维护 $c(p, 0/1), s(p, 0/1)$ 表示取的最优个数和价值即可,查询的时候在线段树上二分

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
const int MaxN = 301234, MaxM = MaxN << 2;
int n, m, ls[MaxN];
pair<int, int> a[MaxN];
struct { int a, k, i;}q[MaxN];
bool cmp(query x, query y) {
return x.a < y.a;
}
int g[MaxM][2], c[MaxM][2]; LL s[MaxM][2];
void modify(int p, int l, int r, int q, int d){
if(l == r){
g[p][0] = c[p][0] = 1; s[p][0] = d;
return;
}
if(q <= l + r >> 1)
modify(p << 1, l, l + r >> 1, q, d);
else
modify(p << 1 | 1, (l + r >> 1) + 1, r, q, d);
for(int o = 0; o < 2; o++){
int t = g[p << 1 | 1][o];
g[p][o] = g[p << 1][t];
c[p][o] = c[p << 1 | 1][o] + c[p << 1][t];
s[p][o] = s[p << 1 | 1][o] + s[p << 1][t];
}
}
LL ans[MaxN];
LL (int p, int l, int r, int k, int o = 0){
if(k >= c[p][o]) return s[p][o];
if(l == r) return 0;
if(k <= c[p << 1 | 1][o])
return query(p << 1 | 1, (l + r >> 1) + 1, r, k, o);
else
return s[p << 1 | 1][o] +
query(p << 1, l, l + r >> 1, k - c[p << 1 | 1][o], g[p << 1 | 1][o]);
}
int main() {
int i, j;
n = inp();
for(i = 1; i <= n; i++)
scanf("%d %d", &a[i].fir, &a[i].sec), ls[i] = a[i].sec;
sort(a + 1, a + n + 1);
sort(ls + 1, ls + n + 1);
m = inp();
for(i = 1; i <= m; i++)
scanf("%d %d", &q[i].a, &q[i].k), q[i].i = i;
sort(q + 1, q + m + 1, cmp);
for(i = 1, j = 1; i <= m; i++){
while(j <= n && a[j].fir <= q[i].a)
modify(1, 1, n, lower_bound(ls + 1, ls + n + 1, a[j].sec) - ls, a[j].sec), j++;
ans[q[i].i] = query(1, 1, n, q[i].k);
}
for(i = 1; i <= m; i++) printf("%lldn", ans[i]);
return 0;
}