在本文中,我们给出了一个整数数组。我们的任务是找到给定范围内所有数字的按位或,例如,
Input: arr[] = {1, 3, 1, 2, 3, 4}, q[] = {{0, 1}, {3, 5}}
Output:
3
7
1 OR 3 = 3
2 OR 3 OR 4 = 7
Input: arr[] = {1, 2, 3, 4, 5}, q[] = {{0, 4}, {1, 3}}
Output:
7
7
登录后复制
在给定的问题中,我们将使用强力方法来解决它,然后检查它是否可以适用于更高的约束。如果没有,那么我们将优化我们的方法以适应更高的约束。
暴力方法
在这种方法中,我们只需遍历每个范围并计算按位或该范围内的所有数字并打印我们的答案。
示例
#include
using namespace std;
int main() {
int arr[] = { 7, 5, 3, 5, 2, 3 };
int n = sizeof(arr) / sizeof(int); // size of our array
int queries[][2] = { { 1, 3 }, { 4, 5 } }; // given queries
int q = sizeof(queries) / sizeof(queries[0]); // number of queries
for(int i = 0; i < q; i++) { // traversing through all the queries
long ans = 0;
for(int j = queries[i][0]; j j) & 1);
for (int i = 1; i < n; i++) {
prefixbits[j][i] = arr[i] & (1LL