Kth Largest Values in a Stream

# Kth Largest Values in a Stream Implement `kth_largest_after_additions(k: int, initial: list[int], additions: list[int]) -> list[int]`. Begin with the values in `initial`. Add the values in `additions` one at a time. After each addition, return the kth largest value among every value seen so far, counting duplicates as separate values. ### Input Domain - `1 <= k <= len(initial) <= 200,000`. - `0 <= len(additions) <= 200,000`. - Every value is a signed 32-bit integer. ### Output Rules - The largest value is the first largest. - Equal values occupy separate rank positions. - Produce one output for every addition in the same order. - Return an empty list when `additions` is empty. ### Constraints - Retain only `O(k)` values beyond the output. - Target time is `O((len(initial) + len(additions)) log k)`. ### Examples #### Example 1 Input: `k = 3, initial = [4,5,8,2], additions = [3,5,10,9,4]` Output: `[4,5,5,8,8]` #### Example 2 Input: `k = 2, initial = [1,1], additions = [1,2,-1]` Output: `[1,1,1]` ```hint Keep the best k values Maintain a structure whose smallest retained value is exactly the current kth largest. ```