<p>You are given a <strong>0-indexed</strong> array <code>nums</code> of length <code>n</code>, consisting of non-negative integers. For each index <code>i</code> from <code>0</code> to <code>n - 1</code>, you must determine the size of the <strong>minimum sized</strong> non-empty subarray of <code>nums</code> starting at <code>i</code> (<strong>inclusive</strong>) that has the <strong>maximum</strong> possible <strong>bitwise OR</strong>.</p>

<ul>
	<li>In other words, let <code>B<sub>ij</sub></code> be the bitwise OR of the subarray <code>nums[i...j]</code>. You need to find the smallest subarray starting at <code>i</code>, such that bitwise OR of this subarray is equal to <code>max(B<sub>ik</sub>)</code> where <code>i &lt;= k &lt;= n - 1</code>.</li>
</ul>

<p>The bitwise OR of an array is the bitwise OR of all the numbers in it.</p>

<p>Return <em>an integer array </em><code>answer</code><em> of size </em><code>n</code><em> where </em><code>answer[i]</code><em> is the length of the <strong>minimum</strong> sized subarray starting at </em><code>i</code><em> with <strong>maximum</strong> bitwise OR.</em></p>

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

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

<pre>
<strong>Input:</strong> nums = [1,0,2,1,3]
<strong>Output:</strong> [3,3,2,2,1]
<strong>Explanation:</strong>
The maximum possible bitwise OR starting at any index is 3. 
- Starting at index 0, the shortest subarray that yields it is [1,0,2].
- Starting at index 1, the shortest subarray that yields the maximum bitwise OR is [0,2,1].
- Starting at index 2, the shortest subarray that yields the maximum bitwise OR is [2,1].
- Starting at index 3, the shortest subarray that yields the maximum bitwise OR is [1,3].
- Starting at index 4, the shortest subarray that yields the maximum bitwise OR is [3].
Therefore, we return [3,3,2,2,1]. 
</pre>

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

<pre>
<strong>Input:</strong> nums = [1,2]
<strong>Output:</strong> [2,1]
<strong>Explanation:
</strong>Starting at index 0, the shortest subarray that yields the maximum bitwise OR is of length 2.
Starting at index 1, the shortest subarray that yields the maximum bitwise OR is of length 1.
Therefore, we return [2,1].
</pre>

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

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

from typing import List
from bisect import bisect_left

class Solution:
    def smallestSubarrays(self, nums: List[int]) -> List[int]:
        n = len(nums)

        # 先找出每個 suffix array 可以 產生的 bit-wise OR 結果
        suffix_or = list(nums)
        for i in reversed(range(n-1)):
            suffix_or[i] |= suffix_or[i+1]

        # print(f'suffix_or={suffix_or}')

        # 整個 array 中全部被設定過的 bits
        one_bits = [i for i in range(32) if suffix_or[0] & (1 << i)]
        # print(f'one_bits={one_bits}')

        # 針對 max_or 中所有被設定的 1 bits, 紀錄可以由 nums 中哪些位置的數字所貢獻
        # 數值的內容在 32 bits 以內，所以使用 32 個 list 來紀錄
        idx_of_bit = [[] for _ in range(32)]

        for i, num in enumerate(nums):
            for b in one_bits:
                if num & (1 << b):
                    idx_of_bit[b].append(i)

        # print(f'idx_of_bit={idx_of_bit}')

        ans = []
        for i, num in enumerate(nums):
            if suffix_or[i] == 0:
                ans.append(1)
                continue

            valid_bit_locs = []
            for b in one_bits:
                # 如果 suffix_or[i] 的 b-bit 有設定，才需要檢查
                if suffix_or[i] & (1 << b):
                    j_idx = bisect_left(idx_of_bit[b], i)
                    valid_bit_locs.append(idx_of_bit[b][j_idx])
            
            j = max(valid_bit_locs)
            ans.append(j - i + 1)

        return ans

if __name__ == "__main__":
    solution = Solution()

    nums = [1,0,2,1,3]
    print(solution.smallestSubarrays(nums))  # [3,3,2,2,1]

    nums = [1,2]
    print(solution.smallestSubarrays(nums))  # [2,1]

    nums = [0]
    print(solution.smallestSubarrays(nums))  # [0]

32400