使用 C++ 查找按位或 >= K 的子数组的数量
c++server side programmingprogramming
在本文中，我们将简要说明如何在 C++ 中解决按位或>=K 的子数组的数量。因此，我们有一个数组 arr[] 和一个整数 K，我们必须找到 OR(按位或)大于或等于 K 的子数组的数量。因此，这里是给定问题的示例 −
输入:arr[] = {1, 2, 3} K = 3
输出:4
子数组的按位或:
{1} = 1
{1, 2} = 3
{1, 2, 3} = 3
{2} = 2
{2, 3} = 3
{3} = 3
4 个子数组具有按位或 ≥ 3
输入:arr[] = {3, 4, 5} K = 6
输出:2
寻找解决方案的方法
现在我们将使用两种不同的方法使用 C++ − 解决问题
强力
在这种方法中，我们将简单地遍历可以形成的所有子数组并检查 OR 是否大于或等于 K。如果是，那么我们将增加我们的答案。
示例
#include <bits/stdc++.h>
using namespace std;
int main(){
int arr[] = {1, 2, 3}; // 给定数组。
int k = 3;
int size = sizeof(arr) / sizeof(int); // 我们数组的大小。
int answer = 0; // 计数器变量。
for(int i = 0; i < size; i++){
int bitwise = 0; // 我们与 k 进行比较的变量。
for(int j = i; j < size; j++){ // 从 i 开始的所有子数组。
bitwise = bitwise | arr[j];
if(bitwise >= k) // 如果 bitwise >= k 增加答案。
answer++;
}
}
cout << answer << "\n";
return 0;
}
输出
4
这种方法非常简单，但也有缺陷，因为这种方法对于更高的约束条件来说不是很好，因为对于更高的约束条件，它会花费太多时间，因为这种方法的时间复杂度是O(N * N)，其中N是给定数组的大小，所以现在我们要采用一种高效的方法。
高效方法
在这种方法中，我们将使用OR运算符的一些属性，即使我们添加更多数字，它也不会减少，所以如果我们得到一个从i到j的子数组，其OR大于或等于K，那么每个包含范围{i，j}的子数组的OR都会大于K，我们正在利用这个属性来改进我们的代码。
示例
#include <bits/stdc++.h>
#define N 1000
using namespace std;
int t[4*N];
void build(int* a, int v, int start, int end){ // 线段树构建
if(start == end){
t[v] = a[start];
return;
}
int mid = (start + end)/2;
build(a, 2 * v, start, mid);
build(a, 2 * v + 1, mid + 1, end);
t[v] = t[2 * v] | t[2 * v + 1];
}
int query(int v, int tl, int tr, int l, int r){//用于处理我们的查询或子数组。
if (l > r)
return 0;
if(tl == l && tr == r)
return t[v];
int tm = (tl + tr)/2;
int q1 = query(2*v, tl, tm, l, min(tm, r));
int q2 = query((2*v)+1, tm+1, tr, max(tm+1, l), r);
return q1 | q2;
}
int main(){
int arr[] = {1, 2, 3}; // 给定数组。
int k = 3;
int size = sizeof(arr) / sizeof(arr[0]); // 数组的大小。
int answer = 0; // 计数器变量。
build(arr, 1, 0, size - 1); // 构建线段树。
for(int i = 0; i < size; i++){
int start = i, end = size-1;
int ind = INT_MAX;
while(start <= end){ // 二分查找
int mid = (start + end) / 2;
if(query(1, 0, size-1, i, mid) >= k){ // 检查子数组。
ind = min(mid, ind);
end = mid - 1;
}
else
start = mid + 1;
}
if(ind != INT_MAX) // 如果 ind 发生变化，则增加答案。
answer += size - ind;
}
cout << answer << "\n";
return 0;
}
输出
4
在这种方法中，我们使用二分搜索和线段树，这有助于将时间复杂度从O(N*N) 降低到 O(Nlog(N))，这非常好。现在，与前一个程序不同，此程序还可以处理更大的约束。
结论
在本文中，我们使用二分搜索和线段树解决了一个问题，即在 O(nlog(n)) 时间复杂度内找到具有 OR >= K 的子数组的数量。我们还学习了此问题的 C++ 程序以及解决此问题的完整方法(常规和高效)。我们可以用其他语言(如 C、java、python 和其他语言)编写相同的程序。希望您觉得本文有用。
