FastPrep
Problem · Segment Tree

Segment Queries

● HardTiktokINTERNNEW GRADOA
See Tiktok hiring insights

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.

Examples
01 · Example 1
cat = [1, 2, 1, 1, 3]
cnt = [5, 3, 4, 5, 2]
l = [1, 1]
r = [3, 5]
return = [8, 7]
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 🛵
More Tiktok problems
drafts saved locally
public int[] segmentQueries(int[] cat, int[] cnt, int[] l, int[] r) {
    // write your code here
}
cat[1, 2, 1, 1, 3]
cnt[5, 3, 4, 5, 2]
l[1, 1]
r[3, 5]
expected[8, 7]
sign in to submit