<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 __init__(self):
        self.table = []
        self.n = 0
    
    def buildSparseTable(self, arr): 
        for i in range(self.n):  
            self.table[i][0] = arr[i]  
        j = 1
        while (1 << j) <= self.n:  
            i = 0
            while i <= self.n - (1 << j):  
                self.table[i][j] = (self.table[i][j - 1] & self.table[i + (1 << (j - 1))][j - 1]) 
                i += 1
            j += 1
 
    def query(self, i, j):  
        import math
        k = int(math.log2(j - i + 1))  
        return (self.table[i][k] & self.table[j - (1 << k) + 1][k]) 
    
    def countSubarrays(self, nums: list[int], k: int) -> int:
        import math
        self.n = len(nums)
        p = int(math.log2(self.n)) + 1
        self.table = [[0]*p for i in range(self.n)]
        self.buildSparseTable(nums)
        vals = [0]*self.n
        ids = [(-1, -1)]*self.n
        vals[-1] = 1 if nums[-1] == k else 0
        ids[-1] = (self.n - 1, self.n - 1) if nums[-1] == k else (-1, -1)
        for m in range(self.n - 2, -1, -1):
            if nums[m] == nums[m+1] == k:
                vals[m] = vals[m+1] + (ids[m+1][1] - m + 1)
                ids[m] = ids[m+1]
            else:
                i, j = m, self.n - 1
                res = -1
                while i <= j:
                    if self.query(m, i) < k or self.query(m, j) > k:
                        break
                    md = (i+j)>>1
                    q = self.query(m, md)
                    if q > k:
                        i = md + 1
                    else:
                        res = md if q == k else -1
                        j = md - 1
                if res > -1:
                    i, j = res, self.n - 1
                    while i <= j:
                        md = (i+j)>>1
                        q = self.query(m, md)
                        if q == k:
                            i = md + 1
                            idx = md
                        else:
                            j = md - 1
                val = 0
                if res > -1:
    #                 print(m, idx, res)
                    val = idx - res + 1
                    ids[m] = (res, idx)
                vals[m] = vals[m+1] + val
    #         print(vals)
        return vals[0]
        
57000