传送门
Solution
并查集。在一个 k 下能通过若干次交换相互得到的物品构成一个集合。
对 q 个询问升序排序，离线处理。
对大小为 n+m 的数组 an 进行排序，枚举 ai，二分查找在哪个询问时合并 ai 和 ai+1 所在集合。
一个集合包含的元素必然在有序数组 an 中构成连续区间。
两个集合合并时，同时更新的信息有：集合的根节点，集合在 an 中的左、右边界，集合中含有多少个初始持有的物品（设为 cnt）。
答案所求为 n 个物品的总和最大值。因此一个集合对答案的贡献为最右边的 cnt 个元素的和。这里采用前缀和直接求出。
合并集合时更新答案，要先减去两个原集合的贡献，再加上新集合的贡献。
Code
数组 bn 记录着每个询问的信息。因为对其二分查找 lower_bound 涉及到该数组元素大小的比较，因此选择运算符重载。
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
| #include <bits/stdc++.h>
#define N 1000010
using namespace std;
typedef long long ll;
template <typename T> inline void read(T &x)
{
x = 0; T f = 1; char ch = getchar();
while (!isdigit(ch)) {if (ch == '-') f = -f; ch = getchar();}
while (isdigit(ch)) {x = x * 10 + ch - 48; ch = getchar();}
x *= f;
}
ll n, m, q, cnt[N], sum[N], ans[N], l[N], r[N], tot, fa[N];
pair<ll, ll> a[N];
struct Query {
ll val, id;
friend bool operator < (const Query &a, const Query &b) {
return a.val < b.val;
}
} b[N];
vector<ll> t[N];
ll find(ll x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}
int main()
{
read(n); read(m); read(q);
for (int i = 1; i <= n + m; i++) {
read(a[i].first);
a[i].second = i;
if (i <= n)
tot += a[i].first;
}
sort(a + 1, a + n + m + 1);
for (int i = 1; i <= q; i++) {
read(b[i].val);
b[i].id = i;
}
sort(b + 1, b + 1 + q);
for (int i = 1; i <= n + m; i++) {
if (i != n + m) {
ll num = lower_bound(b + 1, b + 1 + q, (Query){a[i + 1].first - a[i].first, 0ll}) - b;
t[num].push_back(i);
}
sum[i] = sum[i - 1] + a[i].first;
fa[i] = l[i] = r[i] = i;
cnt[i] = (a[i].second <= n);
}
for (int i = 1; i <= q; i++) {
for (int j = 0; j < t[i].size(); j++) {
ll x = find(t[i][j]), y = find(t[i][j] + 1);
fa[x] = y;
l[y] = l[x];
tot -= sum[r[x]] - sum[r[x] - cnt[x]];
tot -= sum[r[y]] - sum[r[y] - cnt[y]];
cnt[y] += cnt[x];
tot += sum[r[y]] - sum[r[y] - cnt[y]];
}
ans[b[i].id] = tot;
}
for (int i = 1; i <= q; i++)
printf("%lld\n", ans[i]);
return 0;
}
|