2411. Smallest Subarrays With Maximum Bitwise OR

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

• In other words, let Bij be the bitwise OR of the subarray nums[i…j]. You need to find the smallest subarray starting at i, such that bitwise OR of this subarray is equal to max(Bik) where i <= k <= n - 1.

The bitwise OR of an array is the bitwise OR of all the numbers in it.

Return an integer array answer of size n where answer[i] is the length of the minimum sized subarray starting at i with maximum bitwise OR.

A subarray is a contiguous non-empty sequence of elements within an array.

class Solution {
public:
    vector<int> smallestSubarrays(vector<int>& nums) {
        vector<deque<long long>> dq(32);
        vector<long long> freq(32);
        vector<int> res;
        for(int i = 0; i < nums.size(); i++) {
            for(long long bit = 0; bit < 32; bit++) {
                if(nums[i] & (1ll<<bit)) {
                    freq[bit]++;
                    dq[bit].push_back(i);
                }
            }
        }
        for(int i = 0; i < nums.size(); i++) {
            long long ma = i;
            for(int j = 0; j < 32; j++) {
                if(freq[j]) ma = max(ma,dq[j].front());
            }
            res.push_back(ma-i+1);
            for(long long bit = 0; bit < 32; bit++) {
                if(nums[i] & (1ll<<bit)) {
                    freq[bit]--;
                    dq[bit].pop_front();
                }
            }
        }
        return res;
    }
};