<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_or 陣列，用來儲存從 i 開始到陣列結尾的 bit-wise OR 值
        suffix_or = list(nums)  # 初始時每個位置的 OR 值就是該數字本身
        for i in reversed(range(n - 1)):
            # 計算每個索引處的 suffix bit-wise OR
            suffix_or[i] |= suffix_or[i + 1]
        
        # `suffix_or[0]` 代表整個陣列的最大 bit-wise OR
        # 獲取其中所有被設定為 1 的位元
        one_bits = [i for i in range(32) if suffix_or[0] & (1 << i)]

        # `idx_of_bit` 用來記錄每個 bit 出現的位置
        # 這裡是 32 個列表，對應 32 個 bit 位元，每個列表記錄該 bit 為 1 的索引
        idx_of_bit = [[] for _ in range(32)]
        
        # 填充 `idx_of_bit`，每個 bit 的索引位置在哪些數字中出現
        for i, num in enumerate(nums):
            for b in one_bits:
                if num & (1 << b):
                    idx_of_bit[b].append(i)

        # 結果陣列，存放每個位置的最短子陣列長度
        ans = []
        
        for i, num in enumerate(nums):
            # 如果 suffix_or[i] 為 0，表示這個位置的子陣列中 bit-wise OR 為 0
            if suffix_or[i] == 0:
                ans.append(1)
                continue

            # `valid_bit_locs` 儲存所有有效 bit 的最小索引位置
            valid_bit_locs = []
            for b in one_bits:
                # 只考慮在當前 suffix_or[i] 中為 1 的 bit
                if suffix_or[i] & (1 << b):
                    # 使用二分搜尋找到該 bit 第一次出現在索引 i 及之後的位置
                    j_idx = bisect_left(idx_of_bit[b], i)
                    valid_bit_locs.append(idx_of_bit[b][j_idx])
            
            # 子陣列的終點是所有 bit 中最大的有效索引
            j = max(valid_bit_locs)
            # 子陣列的長度為 j - i + 1
            ans.append(j - i + 1)

        return ans

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

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

    # 測試案例 2
    nums = [1, 2]
    print(solution.smallestSubarrays(nums))  # [2,1]

    # 測試案例 3
    nums = [0]
    print(solution.smallestSubarrays(nums))  # [1]

    # 測試案例 4
    nums = [5, 2, 7, 10]
    print(solution.smallestSubarrays(nums))  # [4, 3, 2, 1]

    # 測試案例 5
    nums = [8, 1, 2, 4]
    print(solution.smallestSubarrays(nums))  # [4, 3, 2, 1]

32500