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:
- First, we process all queries offline. We will process k from small to large in order.
- As k increases, we use Disjoint-set to maintain the interval.
- For each interval, we record the index of the rightmost point and the number of items in the interval.
- 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.