Codeforces Round #760 Trader Problem 题解 (Java/C++)

题解

首先，我们可以直接把所有物品一起考虑。

我们考虑下面的例子（我基于样例改了一点点）：

我们考虑k=2时，经过若干次交易之后的结果：

我们仔细观察上面的例子，我们注意到：10-15是连续的一个区间，因为15到18之间的差为3，而10-15之间的所有物品之间的差都不超过k。
而最终的结果，红字必然是从右往左依次排列。
同理18自己是一段，30-31是一段。

现在我们试着把k从2改为3。很自然的，现在整个10-18都会是连续的一整段。于是很自然的：

于是，做法就比较明显了：

1. 首先，我们离线的处理所有的查询。我们将k从小到大依次处理。
2. 随着k的逐步增大，我们使用并查集来维护区间。
3. 对于每个区间，我们记录其最右端的点的下标，以及其区间内物品的数量。
4. 最后，我们维护一个前缀和以便我们在合并两个区间时，快速计算对最终总价值的影响即可。

代码

Java

C++