1959. The Total Of The Top k, While Scores Change

A leaderboard holds a score for each player. Scores are set and overwritten, players leave, and at any moment you need the total of the k highest scores.

set p s player p's score becomes s, replacing any earlier score remove p player p leaves the board top k the total of the k highest scores currently on the board

## What every operation prints

Every operation prints exactly one line.

• set p s prints ok.
• remove p prints the score the player had, or none if that player was not
• on the board, in which case nothing changes.
• top k prints the total. If fewer than k players are on the board it adds
• up all of them, and top 0 prints 0.

top 2 -> 0 set 1 5 -> ok set 2 3 -> ok top 2 -> 8 top 1 -> 5 set 1 1 -> ok player 1's score is replaced, not added to top 2 -> 4 remove 2 -> 3 top 2 -> 1

## Why the incremental trick from problem 1958 does not work here

In 1958 counts only ever rose, so the best k could only change by a value entering, and the entering value was the one in your hand. Here a set can LOWER a score and a remove can take a member out, so the new k-th place can be a player nobody has mentioned for a thousand operations. Maintaining a short list is no longer possible: the information needed to repair it is not local to the operation.

That is the lesson of the pair. What you can maintain incrementally is decided by which direction the quantity can move, not by how clever the bookkeeping is.

## What most people try first

Sort the scores on every top. Correct, and O(P log P) per query with P players on the board.

## Count the scores, do not sort the players

Scores are bounded: 0 to 1000. So instead of a list of players, keep a tally of how many players sit at each score, and walk the tally downwards taking as many as are still needed.

``` SC[p] player p's score HASS[p] whether p is on the board BUCK[s] how many players have exactly score s

set p s: if p is on the board: BUCK[SC[p]] -= 1 leave the old bucket SC[p] = s ; HASS[p] = 1 ; BUCK[s] += 1 remove p: HASS[p] = 0 ; BUCK[SC[p]] -= 1 top k: left = k ; total = 0 for s from 1000 down to 0 while left > 0: take = min(BUCK[s], left) total += take * s left -= take ```

This is the same move as problem 926, which asks for the total of the k largest values in a fixed array and whose lesson is that bounded values let you count instead of sort. The difference is that here the tally has to be MAINTAINED through updates, which is where the leave-the-old-bucket step comes from.

## Why it is correct

The invariant is that BUCK[s] is the number of players p with HASS[p] set and SC[p] = s. Every operation that changes a player's score adjusts exactly two buckets, the one being left and the one being joined, and a remove adjusts only the one being left. No other player moved, so no other bucket can be affected.

The walk is correct because it takes scores in decreasing order, so the players it accounts for are the k highest. take = min(BUCK[s], left) is what makes a bucket that straddles the k-th place contribute only its share: taking the whole bucket would count players below the cut.

## The boundary that breaks a careless implementation

A set on a player already on the board. Joining the new bucket without leaving the old one leaves that player counted twice, so top starts reporting scores that nobody holds. Every test that only ever sets a player once passes.

The second is the straddling bucket. Taking BUCK[s] entirely rather than min(BUCK[s], left) overshoots whenever several players tie at the boundary score, which a test with distinct scores cannot show.

The third is top k for a k larger than the number of players, which must add up everything rather than run off the end, and top 0, which must print 0.

## Overflow

Here the product matters. There can be up to 1000 players, each with a score up to 1000, so the total reaches 10^6, which is comfortably inside a signed 32 bit integer whose limit is 2147483647. The intermediate take * s is at most 1000 * 1000, also small. So this problem genuinely does not overflow, which is worth stating rather than leaving the reader to wonder: it is the bounded score range that keeps it small, and the same code over scores up to 10^9 would need 64 bit.

## Cost

O(1) for set and remove, and O(S) for top where S is the score range, so 1001 steps regardless of how many players there are. The judge cannot enforce that, so sorting the players on each query passes every declared test.

Constraints - `1 ≤ q ≤ 200000` - `1 ≤ p ≤ 1000` - `0 ≤ s ≤ 1000` - `0 ≤ k ≤ 1000` - `set` and `remove` run in `O(1)` and `top` in `O(1001)`, independent of how many players are on the board - the judge cannot enforce that: the declared tests are small and there is no test generator yet, so sorting the players on each query passes them