Description
Solutions
Segment Queries
🤘 INTERN👩‍🎓 NEW GRAD

There are 4 arrays of data. The arrays cat[n] and cnt[n] are each of n integers, and cat[i] relates to cnt[i]. These represent a category and count at each index. There are also two arrays of integers that represent q queries. The arrays l[q] and r[q] contain 1-based indices for the left and right ends of subarrays to consider in cat and cnt.

Process the queries in order. Create an array of q values where answer i relates to query i.

For each query i:

  • Within the subarrays in cat and cnt, determine the maximum cnt for each cat.
  • Store the sum of these maxima as the answer to the query.
  • Clear the cnt values in the range.

After all queries are processed, return the answer array.

Example 1: 

Input:  cat = [1, 2, 1, 1, 3], cnt = [5, 3, 4, 5, 2], l = [1, 1], r = [3, 5]
Output: [8, 7] 
Explanation:

For the first query, the subarrays are cat[1..3] = [1, 2, 1] and cnt[1..3] = [5, 3, 4]. The maximum count for each category is 5 for category 1 and 3 for category 2. The sum of these maxima is 5 + 3 = 8. The cnt values in the range are cleared to [0, 0, 0, 5, 2].
  
For the second query, the subarrays are cat[1..5] = [1, 2, 1, 1, 3] and cnt[1..5] = [0, 0, 0, 5, 2]. The maximum count for each category is 5 for category 1 and 2 for category 3. The sum of these maxima is 5 + 2 = 7. The cnt values in the range are cleared to [0, 0, 0, 0, 0].
  
The answer array is [8, 7].

I am not 100% sure about the output and explanation. If you find anything wrong, pls don't hesitate to tell Groot in our Discord server. Many thanks in advance~

Cheers,
Groot 🛵
Constraints:
    TO-DO
Thumbnail 0
Testcase
Result
Case 1

input:

output: