This is a made up problem, but I was wondering if there is a faster way to solve this.
Given an array $$$A$$$ of length upto $$$10^5$$$, count the number of non-empty subarrays of $$$A$$$ whose length is divisible by the number of distinct elements present in it, i.e. $$$ distinctCount(subarray) \mathrel{|} length(subarray) $$$.
I can't think of any useful optimizations, trying to think with lazy segment trees makes it really complex, my only hope is with either Square-root decomposition, or combining two algorithms for $$$O(N\sqrt{N})$$$ solution.
I was thinking in terms of writing it as $$$length = k * distinctCount$$$ for some integer $$$k$$$, then combining two algorithms for $$$k <> \sqrt{N}$$$, but haven't made much progress.
I am curious so do help me.
Well I suppose it can be done with two pointers. The ideas is for each index we find out largest index j s.t. [a_i ..... a_j] is distinct. Further note that all the subarrays of this array are counted. If j-i+1 == l, then the answer for this we'll be l * (l + 1) / 2. That's the main idea