Segment Queries

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 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 irelates to query $i.$

For each query $t$

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$ :