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.

Example:

n$=5$

q$=2$

cat $=[1,2,1,1,3]$

cnt $=[5,3,4,5,2]$

l $=[1,1]$

r$=[3,5]$

First query $[1,3]$:

Category $1$ has two occurrences, with a maximum count of $5.$ Category $2$ occurs once with a count of $3.$

The answer to the first query is $5+3=8.$ Delete the values within the range and

go to the next query.

Second query $[1,5]$:

Categories $1$ and $3$ each occur once with counts of $5$ and $2.$ The answer to the

second query is $5+2=7.$ Delete the values within the range.

There are no more queries, so return the answer array $[8,7]$

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