## Editorial for Wesley's Anger Contest 5 Problem 3 - Super Squirrel Sisters

Remember to use this editorial 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.

Author: Zeyu

For subtask 1, we can check all possible subarrays and count all the valid ones. To check a subarray's validity, a hashmap or a frequency array of the subarray can be used to count the number of occurrences for every item in the subarray.

Time Complexity: or depending on the time complexity of the subarray check.

For subtask 2, we can build a frequency array of the original frequency array. This will help check if all elements in the subarray have the same number of occurrences.

In order to prevent rebuilding the frequency array for every check, we can observe that many of the subarrays share common prefixes. More specifically, there are subarrays that share a common left point in any point of the array, each increasing the previous subarray's length by . This means that we are only inserting new element in between two subarrays, and the frequency array does not need to be rebuilt for every check.

Counting the number of distinct items can be done with the observation that we are only inserting items and the number of distinct items only increases when the frequency of the item before insertion is at . The time complexity for the subarray check should now be constant time.

Time Complexity: Since we have a constant time check for each subarray, the time complexity is now or depending on the implementation.

For subtask 3, the maximum number of distinct items is . If this is equal to the number of occurrences of every item in the subarray, then there will be items in the subarray. The only valid subarrays we need to check are the ones with a size of .

Time Complexity: Since there are only subarrays that have a size of , the time complexity is .