<p>Given an integer array <code>nums</code> and two integers <code>k</code> and <code>p</code>, return <em>the number of <strong>distinct subarrays,</strong> which have <strong>at most</strong></em> <code>k</code> <em>elements </em>that are <em>divisible by</em> <code>p</code>.</p>

<p>Two arrays <code>nums1</code> and <code>nums2</code> are said to be <strong>distinct</strong> if:</p>

<ul>
	<li>They are of <strong>different</strong> lengths, or</li>
	<li>There exists <strong>at least</strong> one index <code>i</code> where <code>nums1[i] != nums2[i]</code>.</li>
</ul>

<p>A <strong>subarray</strong> is defined as a <strong>non-empty</strong> contiguous sequence of elements in an array.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [<u><strong>2</strong></u>,3,3,<u><strong>2</strong></u>,<u><strong>2</strong></u>], k = 2, p = 2
<strong>Output:</strong> 11
<strong>Explanation:</strong>
The elements at indices 0, 3, and 4 are divisible by p = 2.
The 11 distinct subarrays which have at most k = 2 elements divisible by 2 are:
[2], [2,3], [2,3,3], [2,3,3,2], [3], [3,3], [3,3,2], [3,3,2,2], [3,2], [3,2,2], and [2,2].
Note that the subarrays [2] and [3] occur more than once in nums, but they should each be counted only once.
The subarray [2,3,3,2,2] should not be counted because it has 3 elements that are divisible by 2.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3,4], k = 4, p = 1
<strong>Output:</strong> 10
<strong>Explanation:</strong>
All element of nums are divisible by p = 1.
Also, every subarray of nums will have at most 4 elements that are divisible by 1.
Since all subarrays are distinct, the total number of subarrays satisfying all the constraints is 10.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 200</code></li>
	<li><code>1 &lt;= nums[i], p &lt;= 200</code></li>
	<li><code>1 &lt;= k &lt;= nums.length</code></li>
</ul>

<p>&nbsp;</p>
<p><strong>Follow up:</strong></p>

<p>Can you solve this problem in O(n<sup>2</sup>) time complexity?</p>


# Submitted by Samy Vilar <samy_vilar> on 07/23/2024

# TL;DR: generate the longest common prefix through the suffix array
# then apply a two-pointer approach to determine the furthest successor
# each i could take, accumulating all positive differences between
# each corresponding maximal length and matched prefix;


# long version:
# let D(i) be 1 iff (nums[i] % p) == 0 otherwise 0;
# let F(i) = D(0) + D(1) + ... + D(i)
# then for each i, we will locate the nearest invalid interval;
# i.e. some j s.t. k < F(j) - F(i - 1) but F(j - 1) - F(i - 1) <= k
# intuitively should j < |nums|, then it would imply D(j) must be 1;
# as such at any given time should D(i) == 1 we will move/shift j 
# to either n or the nearest next multiple of p, which ever occurs 
# first;

# Since of the j - i sub-intervals we are only interested in those never
# before seen; we will consider all suffixes of nums and for each we will
# determine the longest common prefix w/ some other suffix;
# intuitively should this be P(i) for i, we increment our solution by
# min(0, j - i - P(i));

# To determine P, we sort the suffixes or equivalently generate the suffix
# array of nums; see the entry at cp-algorithms.com; essentially/informally
# we apply prefix-sort over all the (cyclic) suffixes, though crucially 
# instead of taking unit chunks, we keep doubling our unit lengths; for the most
# part correctness stems from the overlapping nature of (possibly cyclic) 
# suffixes; 

# Given the suffix array would yield the suffixes (stably) ordered 
# lexicographically, it would suffice to count the number of matching 
# symbols across all said neighboring ordering; 
# intuitively the best any suffix could ever hope to match is some
# prefix w/ respect to its neighbor w/i our suffix-array, given
# its lexicographic (ascending) ordering;
# To speed-up (subsequent) searchs we will leverage the duplicity of P(i) 
# along w/ the  aforementioned overlapping nature;
# if at suffix i we matched at most P(i) w/ respect to its neighbor j;
# then it must hold, while considering suffix i + 1, at the very least P(i) - 1 
# symbols can be made to match with some other suffix, given we've
# essentially disregarded the "base" symbol from i; and should there be 
# only 1 possible other suffix then it would imply i's "neighbor" must be
# j + 1, if not then its neighbor could be possibly yield further matches;
# but at the very least it would still match P(i) - 1 symbols otherwise
# our ordering couldn't possibly be valid;

# NOTE both of the aforementioned operations can be made signaficantly
# simpler by appending a ficititous negative inf, while the ladder isn't
# really necessary since the aforementioned entry is only truly
# referenced during the first pass; the second would always guarantee
# at one point or another 2 suffixes would locate a mismatch;

# NOTE depending on the platform, e.g. python we can leverage its
# negative indexing (up to a certain extend) simplifying/speeding up 
# several operation(s);

# Overall this would take O(max(nums) + |nums| * log(|nums|)) time 
# w/ O(|nums| + max(nums)) additional-space if we where to use 
# frequency sort otherwise O(|nums| * log(|nums|)**2) time w/ 
# O(|nums|) additional-space;

# version 1.1 merged the last loops

class Solution:        
    def countDistinct(
        self, nums: List[int], k: int, p: int, rank=-1, prev=-1,
        exhaust=deque(maxlen=0).extendleft
    ) -> int:
        tail = len(nums)
        nums.append(0)
        (order := list(range(cnt := tail + 1))).sort(key=nums.__getitem__)
        ids = [0] * cnt
        ranks = [0] * cnt                
        for at in order:
            if prev != (curr := nums[at]):
                prev = curr
                rank += 1
            ranks[at] = rank                
        for span in map((1).__lshift__, range(tail.bit_length())):
            order[:] = map(span.__rsub__, order) if span + span <= cnt \
                else ((at + cnt) if at < -cnt else at 
                        for at in map(span.__rsub__, order))
            ranks, ids = ids, ranks
            order.sort(key=ids.__getitem__)
            prev = other = rank = -1
            for at in order:                
                if prev != (curr := ids[at]) or other != ids[at + span]:
                    prev = curr
                    other = ids[at + span]                    
                    rank += 1                
                ranks[at] = rank
            if ranks == ids:
                break  
        exhaust(map(ranks.__setitem__, order, count()))                                     
        for tail, item in enumerate(islice(nums, cnt := tail)):
            if not (item % p):
                if not k:
                    break
                k -= 1                
        else:
            k = 0
            tail = cnt
        span = 0
        for at, rank in enumerate(islice(ranks, cnt)):
            if rank < cnt:
                other = order[rank + 1]
                while nums[at + span] == nums[other + span]:
                    span += 1                                          
            if span:
                if 0 < (delta := tail - at - span):
                    k += delta
                span -= 1
            else:
                k += tail - at
            if tail != cnt and not (nums[at] % p):
                while (tail := tail + 1) < cnt and nums[tail] % p:
                    pass
        return k
        
54