## Editorial for An Animal Contest 2 P5 - Koala Carnival

**only**when stuck, and

**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.

**Submitting an official solution before solving the problem yourself is a bannable offence.**

Authors:

,#### Subtask 1

For each query from to , iterate and find the furthest left endpoint such that all stuffed animals from to are unique. We take the maximum of for all .

**Time Complexity:**

#### Subtask 2

To optimize, we use a two pointer approach to determine for all in linear time, moving the right pointer backward only when a non-unique stuffed animal is reached and updating a count array accordingly.

As we did before, we take the maximum of for all .

**Time Complexity:**

#### Subtask 3

As before, we precompute for all . By using of the monotonic property of , the answer for query can be found by binary searching for the right most index such that . All have right endpoints higher than . Thus, we only need the largest distinct subarray with right endpoint in the range . We can perform this query using a range tree like a Segment Tree or a Sparse Table.

**Time Complexity:**

## Comments