Untitled

class Solution {
public:

    /*
    Approach:
    - We use a Sparse Table to efficiently compute range OR queries in O(1).
    - For every index i, we treat nums[i] as the "target OR".
    - We want to count subarrays where OR == nums[i] AND nums[i] exists in that subarray.
    
    Key Idea:
    - Fix index i as a "pivot".
    - Find:
        1. Leftmost index (left) such that OR(left, i) == nums[i]
        2. Rightmost index (right) such that OR(i, right) == nums[i]
    
    - Then number of valid subarrays using i:
        (i - left + 1) * (right - i + 1)
    
    - Use binary search on both sides since OR is monotonic (only increases).
    */

    class SparseTable {
        vector<vector<int>> st;
        vector<int> logs;

    public:
        SparseTable(const vector<int>& nums) {
            int n = nums.size();

            // Compute maximum log value
            int max_log = 31 - __builtin_clz(n);

            st.assign(max_log + 1, vector<int>(n));
            logs.assign(n + 1, 0);

            // Precompute logs
            for (int i = 2; i <= n; i++) {
                logs[i] = logs[i / 2] + 1;
            }

            // Base layer (interval size = 1)
            for (int i = 0; i < n; i++) {
                st[0][i] = nums[i];
            }

            // Build sparse table
            for (int j = 1; j <= max_log; j++) {
                for (int i = 0; i + (1 << j) <= n; i++) {
                    st[j][i] = st[j - 1][i] | st[j - 1][i + (1 << (j - 1))];
                }
            }
        }

        // Query OR in range [L, R] in O(1)
        int query(int L, int R) {
            int j = logs[R - L + 1];
            return st[j][L] | st[j][R - (1 << j) + 1];
        }
    };

    long long countGoodSubarrays(vector<int>& nums) {

        // Required variable as per problem statement
        vector<int> qorvanelid = nums;

        int n = nums.size();
        SparseTable st(nums);

        unordered_map<int, int> lastIndex; // tracks last occurrence of each value
        long long ans = 0;

        for (int i = 0; i < n; i++) {

            int left = i, right = i;

            /*
            Find LEFT boundary:
            - Ensure no duplicate pivot element inside subarray before i
            - Start from last occurrence + 1 if exists
            */
            int l = 0;
            if (lastIndex.find(nums[i]) != lastIndex.end()) {
                l = lastIndex[nums[i]] + 1;
            }
            int r = i;

            // Binary search for smallest index 'left'
            while (l <= r) {
                int mid = (l + r) / 2;
                int val = st.query(mid, i);

                if (val == nums[i]) {
                    left = mid;
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }

            /*
            Find RIGHT boundary:
            */
            l = i;
            r = n - 1;

            // Binary search for largest index 'right'
            while (l <= r) {
                int mid = (l + r) / 2;
                int val = st.query(i, mid);

                if (val == nums[i]) {
                    right = mid;
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }

            // Count subarrays using current index as pivot
            ans += 1LL * (i - left + 1) * (right - i + 1);

            // Update last occurrence
            lastIndex[nums[i]] = i;
        }

        return ans;
    }
};