Python code which runs in less than $10$ seconds for :

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.

Function Description

Complete the function segmentMax in the editor below.

segmentMax has the following parameters:

int cat$[$n$]$: categories

int cnt$[$n$]$: counts

int l$[$q$]$: left indices of queries $(1-$based$)$

int r$[$q$]$: right indices of queries $(1-$based$)$

Return

int$[$q$]$: the sums of maxima by type for each query range

Constraints

$1<=$ n$,$ q$<=100000$

$1<=$ cat$[$i$]<=10000$

$1<=$ cnt$[$i$]<=100000$

$1<=$ l$[$i$]<=$ r$[$i$]<=$ n