题目:
找出有几个不同的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