<p>Given an array of integers <code>nums</code> and an integer <code>k</code>, return the number of <span data-keyword="subarray-nonempty">subarrays</span> of <code>nums</code> where the bitwise <code>AND</code> of the elements of the subarray equals <code>k</code>.</p>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [1,1,1], k = 1</span></p>

<p><strong>Output:</strong> <span class="example-io">6</span></p>

<p><strong>Explanation:</strong></p>

<p>All subarrays contain only 1&#39;s.</p>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [1,1,2], k = 1</span></p>

<p><strong>Output:</strong> <span class="example-io">3</span></p>

<p><strong>Explanation:</strong></p>

<p>Subarrays having an <code>AND</code> value of 1 are: <code>[<u><strong>1</strong></u>,1,2]</code>, <code>[1,<u><strong>1</strong></u>,2]</code>, <code>[<u><strong>1,1</strong></u>,2]</code>.</p>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [1,2,3], k = 2</span></p>

<p><strong>Output:</strong> <span class="example-io">2</span></p>

<p><strong>Explanation:</strong></p>

<p>Subarrays having an <code>AND</code> value of 2 are: <code>[1,<b><u>2</u></b>,3]</code>, <code>[1,<u><strong>2,3</strong></u>]</code>.</p>
</div>

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

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= nums[i], k &lt;= 10<sup>9</sup></code></li>
</ul>

"""
    update nums array when iterating
    such as when visit i
        nums[j] = AND(nums[j] .. nums[i])
    
    for i in range(0, n):
        for j in range(i-1, -1, -1):
            for nums[j] it's non incresing, because it's AND nums[i], i+1 etc... 
                - as i increase, first and last occurence of nums[j] = k (l and r) will move right
                - can use 3 pointers to move l, r to right
            for nums[j] ... nums[i]       it's non decreasing
                - bianry search to find the first and last k's position l, r
                - monotonic -> keep moving l, r 
            O(n^2)
            key point: when can we break the inner loop
            if nums[j] & x == nums[j] 
                - nums[j] and it's left side will no longer decrease
            it means no longer need to update the left part of j
        
    M1: 二分
    Time: O(n log u + n log n) u is the max(nums) so logU is the # of bit for u, nlog n is for binary search
    Space: O(1)

    M2: 滑动窗口
    Time: O(n log u)
    Space: O(1)

    M3: 动态维护
    Time: O(n log u)
    Space: O(1)
"""
class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        ans = 0
        #l = r = 0
        cnt = 0
        for i, x in enumerate(nums):
            if x == k: cnt += 1
            for j in range(i-1, -1, -1):
                if nums[j] & x == nums[j]:    
                    break
                #nums[j] &= x

            # M1
            # bianry seach the first / last occurence of k
            #l = bisect_left(nums, k, 0, i+1)
            #r = bisect_left(nums, k+1, 0, i+1)     

            # M2
            # while l <= i and nums[l] < k:
            #     l += 1
            # while r <= i and nums[r] <= k:
            #     r += 1

            # # [l, r)
            # ans += r - l

            # M3
                if nums[j] == k:     # after and x, will not < k 
                    cnt -= 1
                nums[j] &= x
                if nums[j] == k:
                    cnt += 1
            ans += cnt
        return ans
888