<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>

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        # a a b * ? * ? a 
#         ans = 0
#         for i in range(len(nums)):
#             for j in range(i, len(nums)):
#                 cur = nums[i]
#                 arr = []
#                 for x in range(i, j + 1):
#                     arr.append(nums[x])
#                     cur &= nums[x]
#                 if cur == k:
#                     print(cur, arr)
#                     ans += 1
#         print("-----")
#         return ans
                    
                    
        
        def solve(arr):
            # print(arr)
            l = r = ret = r2 = 0
            cur = arr[0]
            while r < len(arr):
                # print(cur, arr[r])
                cur &= arr[r]
                if cur == k:
                    cur2 = arr[r]
                    r2 = r
                    while cur2 != k:
                        r2 -= 1
                        cur2 &= arr[r2]
                    lelem = r2 - l
                    relem = len(arr) - r - 1
                    ret += (lelem+1)*(relem+1)
                    # print("before", r, ret, cur, l, r2, lelem, relem)
                    l = r2 + 1
                    if l < len(arr):
                        cur = arr[l]
                        for x in range(l, r + 1):
                            cur &= arr[x]
                # print(r, ret, cur, l, r2)
                r += 1
            return ret
        ans = 0
        left = right = -1
        for i in range(len(nums)):
            if (k & nums[i]) == k:
                if left == -1:
                    left = i
                right = i
            else:
                if left != -1:
                    ans += solve(nums[left:right+1])
                left = -1
        if left != -1:
            ans += solve(nums[left:1+right])
        # print("----")
        return ans
            
512