题解
首先，我们可以直接把所有物品一起考虑。
我们考虑下面的例子（我基于样例改了一点点）：
我们考虑k=2时，经过若干次交易之后的结果：
我们仔细观察上面的例子，我们注意到：10-15是连续的一个区间，因为15到18之间的差为3，而10-15之间的所有物品之间的差都不超过k。
而最终的结果，红字必然是从右往左依次排列。
同理18自己是一段，30-31是一段。
现在我们试着把k从2改为3。很自然的，现在整个10-18都会是连续的一整段。于是很自然的：
于是，做法就比较明显了：
- 首先，我们离线的处理所有的查询。我们将k从小到大依次处理。
- 随着k的逐步增大，我们使用并查集来维护区间。
- 对于每个区间，我们记录其最右端的点的下标，以及其区间内物品的数量。
- 最后，我们维护一个前缀和以便我们在合并两个区间时，快速计算对最终总价值的影响即可。
代码
Java
Submission #140900904 - Codeforces
Codeforces. Programming competitions and contests, programming community
C++
Submission #140903723 - Codeforces
Codeforces. Programming competitions and contests, programming community