Mark Elements on Array by Performing Queries
You are given a 0-indexed array nums of size n consisting of positive integers.
You are also given a 2D array queries of size m where queries[i] = [index_i, k_i].
Initially all elements of the array are unmarked.
You need to apply m queries on the array in order. For the i^th query:
- Mark the element at index
index_iif it is not already marked. - Then mark
k_iunmarked elements in the array with the smallest values. - If multiple such elements exist, mark the ones with the smallest indices.
- If fewer than
k_iunmarked elements exist, mark all of them.
Return an array answer of size m where answer[i] is the sum of unmarked elements in the array after the i^th query.
Example 1
Input
nums = [1,2,2,1,2,3,1], queries = [[1,2],[3,3],[4,2]]Output
[8,3,0]After the three queries, the sums of unmarked elements are 8, then 3, then 0.
Example 2
Input
nums = [1,4,2,3], queries = [[0,1]]Output
[7]The query marks index 0 and then the smallest unmarked element, leaving unmarked elements 4 and 3 with sum 7.
Constraints
- n == nums.length
- m == queries.length
- 1 <= m <= n <= 10^5
- 1 <= nums[i] <= 10^5
- queries[i].length == 2
- 0 <= indexi, ki <= n - 1