CF1618G Trader Problem 题解
提供一个在线做法。
分析1
我们不妨把 \(a\) 和 \(b\) 合并为一个序列，称合并后的序列为 \(c\)，并将其不降序排序。把玩样例后不难发现：对于一个物品序列 \(c_1, c_2, \cdots, c_l\)，满足 \(\forall i < l, c_{i+1} - c_i \le k\)（即任意两个相邻的物品都可以交换），要使最后的总价值最大，最优的方法显然是把初始物品一直往后换。如果在这个序列中我们一开始有 \(cnt\) 个物品，那么交换完之后我们的总价值就是 \(\sum_{i=l-cnt+1}^{l} c_i\)，即最后 \(cnt\) 个物品的价值和。
分析2
上面的分析中，我们假设对于某个特定的 \(k\)，序列满足任意两个相邻的物品可以交换。但如果序列不满足这个性质呢？不难想到，可以把序列断开：对于所有满足 \(c_{i+1} - c_i > k\) 的 \(i\) （也就是说第 \(i\) 个物品不能与第 \(i+1\) 个物品交换），我们就让 \(i\) 和 \(i+1\) 分别属于两个链（子序列）。这样对于每个条链，都满足它任意两个相邻的物品可以交换。把所有链的答案加起来就是总答案。于是，对于每次询问，我们都可以 \(O(n)\) 扫一遍解决。
单次询问 \(O(n)\) 的代码如下：
// mark[i]: 第i个物品是否是一开始手里拥有的
// cnt: 当前这条链中有多少个物品时一开始就有的
void solve(int k)
{
int pos = 2, lst = 1, cnt = mark[1];
ll ans = 0;
for(; pos <= tot; pos++)
{
if(c[pos] - c[pos-1] > k) // 如果这两个相邻的物品不能交换，就断开，统计上一段的贡献
{
ans += sum[pos - 1] - sum[pos - cnt - 1];
lst = pos, cnt = 0;
}
cnt += mark[pos];
}
cout << ans << endl;
}
分析3
上面我们一直默认 \(k\) 为定值，如果 \(k\) 不确定，有没有什么办法能一次处理好所有可能的 \(k\) 对应的答案呢？
首先明确一个问题：虽然 \(k\) 有很多种取值（\(0 \le k \le 10^9\)），但并不是每个不同的 \(k\) 都对应不同的答案。可以这样理解：假设现在我们已经对于某个特定的 \(k\) 把原序列断成了几条链，然后让 \(k\) 不断增大，只有当 \(k\) 可以“跨越”某两条链之间的间隔时，这两条链才会合并到一起，同时答案才可能发生改变。因此，实际上我们并不需要对所有的 \(k\) 都算一个答案。设所有的相邻物品价值差的集合为 \(dif\)，我们只需要让 \(k\) 取遍 \(dif\) 中的每个值即可。将 \(dif\) 排序，设 \(k = dif_i\) 时的答案为 \(ans_i\)。对于每次询问的 \(k\)，二分找出一个 \(i\) 使得 \(dif_i \le k < dif_{i+1}\) ，答案便为 \(ans_i\)。
接下来的做法便不难想到了。一开始令 \(k = 0\)，这时每个物品都只能和与它价值相同的物品构成链，因为任意两个价值不同的物品都不能交换。当 \(k \in [0, dif_1)\) 时，总不会有新的可以交换的物品对产生。只有当 \(k = dif_1\) 时，才可以进行合并。同理，我们继续让 \(k\) 取遍所有的 \(dif_i\)，每次都合并所有可以合并的链，同时统计答案。
可以使用并查集维护链。同时维护每条链包含的初始物品数。合并时，新链的初始物品数即为原来两条链的初始物品数之和。
时间复杂度
（因为 \(n\) 和 \(m\) 数量级相同，下面把所有的 \(n + m\) 都当作 \(n\)。）
因为总共只会合并 \(n-1\) 次，所以统计答案的时间复杂度为 \(O(n)\)。而先前对 \(c\) 排序的时间复杂度为 \(O(n \log n)\)，单次查询的时间复杂度为 \(O(\log n)\)，所以总的时间复杂度为 \(O(n \log n)\)。
代码
// CF1618G Trader Problem
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int MAXN = 2e5 + 10;
int n, m, q, p, a[MAXN], b[MAXN];
int tot, c[MAXN << 1], dif[MAXN << 1], cnt[MAXN << 1];
// cnt[i]: 以i结尾的链中的原始商品的数量
ll sum[MAXN << 1], ans[MAXN << 1];
bool mark[MAXN << 1];
struct Node
{
ll dif;
int pos; // c[pos+1] - c[pos] = dif
Node(int dif, int pos): dif(dif), pos(pos) {}
bool operator > (const Node &rhs) const
{
return dif > rhs.dif;
}
};
priority_queue<Node, vector<Node>, greater<Node>> que;
struct DSU
{
int fa[MAXN << 1];
void init()
{
for(int i = 1; i <= tot; i++)
{
fa[i] = i;
cnt[i] = mark[i];
}
}
int getfa(int u)
{
return fa[u] == u ? u : fa[u] = getfa(fa[u]);
}
void merge(int x, int y) // x < y
{
int fx = getfa(x), fy = getfa(y);
fa[fx] = fy;
cnt[fy] += cnt[fx], cnt[fx] = 0;
}
}dsu;
void merge() // 直接 sort 应该也行
{
int i = 1, j = 1, k = 1;
while(i <= n && j <= m)
{
if(a[i] <= b[j]) mark[k] = true, c[k++] = a[i++];
else c[k++] = b[j++];
}
while(i <= n) mark[k] = true, c[k++] = a[i++];
while(j <= m) c[k++] = b[j++];
for(int i = 1; i <= tot; i++) sum[i] = sum[i-1] + c[i];
for(int i = 1; i < tot; i++)
{
dif[i] = c[i+1] - c[i];
que.push(Node(dif[i], i));
}
sort(dif + 1, dif + tot);
dif[0] = unique(dif + 1, dif + tot) - dif - 1;
}
inline int getrk(int x)
{
return lower_bound(dif + 1, dif + dif[0] + 1, x) - dif;
}
void solve()
{
merge();
dsu.init();
for(int i = 1; i <= n; i++) ans[0] += a[i];
while(!que.empty()) // 这里用优先队列维护 dif，实际上直接把 dif 排序再枚举应该也可以
{
Node u = que.top();
que.pop();
int nowdif = u.dif, rk = getrk(nowdif);
int ori = dsu.getfa(u.pos), tail = dsu.getfa(u.pos + 1);
if(!ans[rk]) ans[rk] = ans[rk - 1];
// 因为没有对 dif 去重，所以第一次遇到 dif 时要先取用上一个 dif 的 ans
ll d1 = (sum[ori] - sum[ori - cnt[ori]]) + (sum[tail] - sum[tail - cnt[tail]]);
dsu.merge(u.pos, u.pos + 1);
ll d2 = sum[tail] - sum[tail - cnt[tail]];
ans[rk] = ans[rk] - d1 + d2;
// 去除原先两条链的贡献，加上新链的贡献
}
}
signed main()
{
cin >> n >> m >> q;
tot = n + m;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= m; i++) cin >> b[i];
sort(a + 1, a + n + 1), sort(b + 1, b + m + 1);
solve();
while(q--)
{
cin >> p;
int rk = upper_bound(dif + 1, dif + dif[0] + 1, p) - dif - 1;
cout << ans[rk] << endl;
}
return 0;
}