LeetCode 898. 子数组按位或操作（前缀和思想）

示例 1：
输入：[0]
输出：1
解释：
只有一个可能的结果 0 。

示例 2：
输入：[1,1,2]
输出：3
解释：
可能的子数组为 [1]，[1]，[2]，[1, 1]，[1, 2]，[1, 1, 2]。
产生的结果为 1，1，2，1，3，3 。
有三个唯一值，所以答案是 3 。

示例 3：
输入：[1,2,4]
输出：6
解释：
可能的结果是 1，2，3，4，6，以及 7 。
 
提示：
1 <= A.length <= 50000
0 <= A[i] <= 10^9

class Solution { // 超时
public:
    int subarrayBitwiseORs(vector<int>& arr) {
        int n = arr.size();
        unordered_set<int> a, b, ans;
        for(int i = 0; i < n; ++i)
        {
            b.clear();
            b.insert(arr[i]);
            for(auto it = a.begin(); it != a.end(); ++it)
            {
                b.insert(*it|arr[i]);
            }
            a.swap(b);
            for(auto i : a)
                ans.insert(i);
        }
        return ans.size();
    }
};

class Solution {
public:
    int subarrayBitwiseORs(vector<int>& arr) {
        int n = arr.size();
        unordered_set<int> ans;
        for(int i = 0; i < n; ++i)//以 i 为右端点
        {
            ans.insert(arr[i]);
            for(int j = i-1; j >= 0; --j) // j 为左端点
            {
                if((arr[j]|arr[i])==arr[j])
                    break;//arr[j] 存储的是 [j, i-1] 的区间 | 和
                arr[j] |= arr[i]; //现在 arr[j] 存储的是 [j, i] 的区间 | 和
                ans.insert(arr[j]);
            }
        }
        return ans.size();
    }
};