題目:
找出有幾個不同的subarray裡面的值or出來的值
思路:
記錄之後下一個會出現的所有bit的位子
在每一個數字檢查的時候
都只要檢查下一次會出現哪些bit
然後or起來就好
因為是int進行or的關係
只要檢查32個就好
這大概是N log32吧
這題我思路好像蠻酷的
給你們看一下
```cpp
class Solution {
public:
int subarrayBitwiseORs(vector<int>& arr)
{
int n = arr.size();
vector<deque<int>> save(32,deque<int>());
unordered_set<int> savenum;
for(int i = 0 ; i < n ; i ++)
{
for(int b = 0 ; b < 32 ; b ++)
{
if((arr[i] >> b) & 1)save[b].push_back(i);
}
}
for(int i = 0 ; i < n ; i ++)
{
for(int b = 0 ; b < 32 ; b ++)
{
if(!save[b].empty() && save[b].front() <= i)
{
save[b].pop_front();
}
}
// idx pow
vector<pair<int,int>> now;
for(int b = 0 ; b < 32 ; b ++)
{
if(arr[i] >> b & 1)continue;
if(!save[b].empty())
{
now.push_back({save[b].front(),b});
}
}
sort(now.begin() , now.end());
if(savenum.find(arr[i]) == savenum.end())savenum.insert(arr[i]);
int cur = arr[i];
int nn = now.size();
int idxnow = i;
for(int j = 0 ; j < nn ; j ++)
{
idxnow = now[j].first;
while(j < nn && idxnow == now[j].first)
{
cur |= 1 << now[j].second ;
j++;
}
j