题解 CF1618G Trader Problem

传送门

Solution

并查集。在一个 $k$ 下能通过若干次交换相互得到的物品构成一个集合。

对 $q$ 个询问升序排序，离线处理。

对大小为 $n+m$ 的数组 $a_n$ 进行排序，枚举 $a_i$，二分查找在哪个询问时合并 $a_i$ 和 $a_{i+1}$ 所在集合。

一个集合包含的元素必然在有序数组 $a_n$ 中构成连续区间。

两个集合合并时，同时更新的信息有：集合的根节点，集合在 $a_n$ 中的左、右边界，集合中含有多少个初始持有的物品（设为 $cnt$）。

答案所求为 $n$ 个物品的总和最大值。因此一个集合对答案的贡献为最右边的 $cnt$ 个元素的和。这里采用前缀和直接求出。

合并集合时更新答案，要先减去两个原集合的贡献，再加上新集合的贡献。

Code

数组 $b_n$ 记录着每个询问的信息。因为对其二分查找 lower_bound 涉及到该数组元素大小的比较，因此选择运算符重载。

#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()
{
	//freopen("a.txt", "r", stdin);
	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;
}