<p>Given an integer array <code>arr</code>, return <em>the number of distinct bitwise ORs of all the non-empty subarrays of</em> <code>arr</code>.</p>

<p>The bitwise OR of a subarray is the bitwise OR of each integer in the subarray. The bitwise OR of a subarray of one integer is that integer.</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> arr = [0]
<strong>Output:</strong> 1
<strong>Explanation:</strong> There is only one possible result: 0.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> arr = [1,1,2]
<strong>Output:</strong> 3
<strong>Explanation:</strong> The possible subarrays are [1], [1], [2], [1, 1], [1, 2], [1, 1, 2].
These yield the results 1, 1, 2, 1, 3, 3.
There are 3 unique values, so the answer is 3.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> arr = [1,2,4]
<strong>Output:</strong> 6
<strong>Explanation:</strong> The possible results are 1, 2, 3, 4, 6, and 7.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= arr.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>0 &lt;= arr[i] &lt;= 10<sup>9</sup></code></li>
</ul>

constexpr int MAXN = 100010;
constexpr int MAXM = 32;

struct RMQ {
  int c[20][MAXN], w[MAXN];

  void Reset(const int* a, int n) {
    w[0] = -1;
    for (int i = 1; i <= n; ++i) {
      w[i] = (i & (i - 1)) ? w[i - 1] : w[i - 1] + 1;
    }
    copy(a, a + n, c[0]);
    for (int d = 1; (1 << d) <= n; ++d) {
      for (int i = 0; i + (1 << d) <= n; ++i) {
        c[d][i] = (c[d - 1][i] | c[d - 1][i + (1 << (d - 1))]);
      }
    }
  }

  int Query(int l, int r) const {
    int d = w[r - l];
    return (c[d][l] | c[d][r - (1 << d)]);
  }
} rmq;

int a[MAXN], pre[MAXM];
unordered_set<int> st;

void Update(int k, int x) {
  for (int i = 0; i <= 30; ++i) {
    if ((x >> i) & 1) {
      pre[i] = k;
    } else if (~pre[i]) {
      st.insert(rmq.Query(pre[i], k + 1));
    }
    st.insert(x);
  }
}

class Solution {
public:
    int subarrayBitwiseORs(vector<int>& arr) {
      int n = arr.size();
      copy(arr.begin(), arr.end(), a);
      rmq.Reset(a, n);
      memset(pre, -1, sizeof(pre));
      st.clear();
      for (int i = 0; i < n; ++i) {
        Update(i, a[i]);
      }
      return st.size();
    }
};
92612