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

Solution:

First, we can directly consider all items together.

Let's consider the following example (I modified it a little bit based on the sample data):

We consider the result after several exchanges when k=2:

We carefully observe the above example, we noticed: 10-15 is a continuous interval, because the difference between 15 and 18 is 3, and the difference between all items between 10-15 does not exceed k.
In the end, the red letters must be arranged in order from right to left.
Similarly, 18 itself is a interval, and 30-31 is a interval.

Now we try to change k from 2 to 3. Naturally, now the entire 10-18 will be a continuous whole interval. So it is natural:

Therefore, the solution is more obvious:

1. First, we process all queries offline. We will process k from small to large in order.
2. As k increases, we use Disjoint-set to maintain the interval.
3. For each interval, we record the index of the rightmost point and the number of items in the interval.
4. Finally, we maintain a prefix sum so that we can quickly calculate the impact on the final total value when we merge the two intervals.

Code:

Java

C++