Bitwise ORs of Subarrays trong C++

Cho mảng A số không âm. Với mọi subarray liên tiếp B = A[i..j], tính OR bitwise của tất cả phần tử. Đếm số kết quả khác nhau.

Ví dụ: [1,1,2] → 3 (subarray: [1],[1],[2],[1,1],[1,2],[1,1,2] → OR: 1,1,2,1,3,3 → distinct: 1,2,3).

Giải pháp:

• Dùng 2 set: ret (kết quả tất cả), curr2 (OR kết thúc tại i-1)

• Duyệt i=0..n-1:
  curr1 = {A[i]}
  Với e trong curr2: curr1.insert(e | A[i])
  Thêm tất cả curr1 vào ret
  curr2 = curr1

• Trả về ret.size()

Độ phức tạp O(n * log(max)) vì số giá trị OR khác nhau tại mỗi vị trí bị giới hạn bởi số bit.

Ví dụ

#include <bits/stdc++.h> using namespace std; class Solution {    public:    int subarrayBitwiseORs(vector<int>& A) {       unordered_set <int> ret, curr2;       for(int i = 0; i < A.size(); i++){          unordered_set <int> curr1; curr1.insert(A[i]);          for(int e : curr2) curr1.insert(e | A[i]);          for(int e : curr1) ret.insert(e);          curr2 = curr1;       }       return ret.size();    } }; int main(){ vector<int> v = {1,1,2}; Solution ob; cout << ob.subarrayBitwiseORs(v); }

Đầu vào

[1,1,2]

Đầu ra

3