Subtask 1

For subtask 1, we can check all possible ~\mathcal{O}(N^2)~ 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: ~\mathcal{O}(N^3)~ or ~\mathcal{O}(N^3 \cdot \log N)~ depending on the time complexity of the subarray check.

Subtask 2

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 ~\mathcal{O}(N^2)~ subarrays share common prefixes. More specifically, there are ~\mathcal{O}(N)~ subarrays that share a common left point in any point of the array, each increasing the previous subarray's length by ~1~. This means that we are only inserting ~1~ 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 ~0~. 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 ~\mathcal{O}(N^2)~ or ~\mathcal{O}(N^2 \cdot \log N)~ depending on the implementation.

Subtask 3

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

Time Complexity: Since there are only ~\mathcal{O}(N)~ subarrays that have a size of ~4~, the time complexity is ~\mathcal{O}(N)~.

Subtask 4

For the full solution, we'll need to combine both observations from subtasks 2 and 3. To generalize subtask 3, only subarrays with the length of a square number will be valid, and we can show that there are only ~\mathcal{O}(\sqrt{N})~ possible distinct subarray lengths.

To generalize the method used in subtask 2, we can check subarrays of a fixed size instead. After inserting the rightmost element into the frequency array, we will remove the leftmost element from the frequency array.

Note that in order to be well below the given time limit, we can completely omit the second frequency array since we know that all items in a subarray of size ~K~ must appear ~\sqrt{K}~ times. It is also important to use vectors or arrays to build the frequency array due to their significantly smaller constant for indexing items.

Time Complexity: ~\mathcal{O}(N \cdot \sqrt{N})~