926. The Total of the k Largest, Many Times

You are given n values, each between 0 and 100000. Then q questions arrive, each a number k. For each question print the total of the k largest values.

``` values 3 1 4 1 5 9, questions k = 1, 3, 6 -> 9 / 18 / 23

values 7 7 7 7, questions k = 2, 4 -> 14 / 28 ```

## The heap answer, and why it is the wrong tool here

The reflex is a bounded heap: sweep the values keeping the k largest in a min-heap, then total it. That is O(n log k) and it is a fine answer to ONE question.

It is the wrong tool here for two separate reasons.

First, it answers one k and then has to start again. With q = 2 * 10^5 questions over n = 2 * 10^5 values, rebuilding the heap each time is 2 * 10^5 * 2 * 10^5 * 17, about 6.8 * 10^11 operations.

Second, and this is the part worth remembering, the VALUE RANGE is small. Every value fits in 0 ... 100000. That single line in the constraints is an invitation, and the method it points at is cheaper than the heap even for a single question.

## The method: counting sort, then one prefix total

cnt[v] = how many times v appears, for v in 0 ... 100000 walk v from 100000 down to 0, writing out cnt[v] copies of v, building pref[j] = the total of the j largest as you go answer for k is pref[k]

Building cnt is O(n). Walking the range and building pref is O(n + V) where V = 100001. Every question is then a single array lookup, so the whole run is

O(n + V + q) about 2*10^5 + 10^5 + 2*10^5 = 5 * 10^5 operations

against 6.8 * 10^11 for the repeated heap. That is not a constant factor.

## When the heap IS right, so the lesson transfers

The comparison is not "heaps are bad". A heap of size k wins whenever

· the values are not integers, or span a range too wide to index · they arrive as a stream and cannot all be held · only one k is ever asked, and n log k beats n + V

With values up to 10^9 the count array would need four gigabytes and the heap is the only option. With values up to 10^5 and several questions, the count array wins outright. The constraint on the VALUE RANGE, not the one on n, is what decides it, and that is the line most people skip.

## Why the prefix total is correct

The k largest values are the first k of the sequence written in decreasing order, whatever the ties, because any two orderings of equal values give the same multiset. So pref[k], the total of the first k written, is the answer.

The walk writes each value exactly cnt[v] times, so it writes n values in non-increasing order, which is a counting sort with the direction reversed.

## The boundary that breaks a careless implementation

pref must be indexed from 0, with pref[0] = 0, so that a question of k = n reads the last entry rather than one past the end.

The count array needs 100001 entries, not 100000, because 0 is a legal value and so is 100000. Allocating 100000 overruns on the largest input.

Walking upwards instead of downwards builds the total of the k SMALLEST, which is a different question and produces plausible-looking wrong answers.

## Overflow

2 * 10^5 values of 10^5 total 2 * 10^10. A signed 32-bit integer holds 2147483647, so the prefix array must be 64-bit. Each individual value fits in 32 bits, and so does k.

No declared test here reaches that total, because an input large enough to do so would be hundreds of kilobytes of literal text. The claim above is arithmetic on the stated limits rather than something the judge enforces, and it is worth being explicit about which of the two you are reading.

## Related problems

Problem #719 trades an unbounded structure for a bounded value range in exactly the same way, using a Fenwick tree over counts because it needs ranks inside a sliding window rather than a prefix total over the whole array. Problem #925 is the bounded-heap version of one question, asked after every arrival, where no count array helps because the answer is wanted n times during the stream.

## Cost

Time O(n + V + q). Space O(n + V).

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ value ≤ 100000` - `1 ≤ q ≤ 200000` - `1 ≤ k ≤ n`