C++를 사용하여 인덱스 범위 내에서 지정된 배열의 비트별 OR 연산을 쿼리합니다.

이 기사에서는 정수 배열이 제공됩니다. 우리의 임무는 주어진 범위에 있는 모든 숫자의 비트 OR을 찾는 것입니다(예:

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

). 주어진 문제에서 우리는 무차별 대입 접근법을 사용하여 문제를 해결한 다음 더 높은 제약 조건에 적용될 수 있는지 확인합니다. 그렇지 않은 경우 더 높은 제약 조건에 맞게 방법을 최적화합니다.

무차별 대입 방법

이 방법에서는 각 범위를 반복하고 해당 범위의 비트 단위 또는 모든 숫자를 계산하고 답을 인쇄합니다.

Example

#include <bits/stdc++.h>
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 <= queries[i][1]; j++) // traversing through the range
         ans |= arr[j]; // calculating the answer
      cout << ans << "\n";
   }
   return 0;
}

Output

7
3

이 접근 방식의 시간 복잡도는 O(N*Q)입니다. 여기서 N은 배열의 크기이고 Q는 현재 쿼리 수입니다. 보시다시피 이 복잡성은 적용되지 않습니다. 더 높은 제약 조건에 대해 이제 더 높은 제약 조건에도 작동하도록 방법을 최적화하겠습니다.

효율적인 방법

이 방법에서는 접두사 숫자의 수를 세고 숫자에 특정 비트 세트가 있는지 확인합니다. 그렇다면 우리는 이 점을 답에 넣습니다. 그렇지 않으면 이 점을 유지합니다.

예제

#include <bits/stdc++.h>

using namespace std;
#define bitt 32
#define MAX (int)10e5

int prefixbits[bitt][MAX];
void bitcount(int *arr, int n) { // making prefix counts
   for (int j = 31; j >= 0; j--) {
      prefixbits[j][0] = ((arr[0] >> j) & 1);
      for (int i = 1; i < n; i++) {
         prefixbits[j][i] = arr[i] & (1LL << j);
         prefixbits[j][i] += prefixbits[j][i - 1];
      }
   }
   return;
}
int check(int l, int r) { // calculating the answer
   long ans = 0; // to avoid overflow we are taking ans as long
   for (int i = 0; i < 32; i++) {
      int x;
      if (l == 0)
         x = prefixbits[i][r];
      else
         x = prefixbits[i][r] - prefixbits[i][l - 1];
      if (x != 0)
         ans = (ans | (1LL << i));
   }
   return ans;
}
int main() {
   int arr[] = {7, 5, 3, 5, 2, 3};
   int n = sizeof(arr) / sizeof(int); // size of our array
   bitcount(arr, n);
   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++) {
      cout << check(queries[i][0], queries[i][1]) << "\n";
   }
   return 0;
}

출력

7
3

이 방법의 시간 복잡도는 O(N)입니다. 여기서 N은 배열의 크기이므로 이 방법은 더 높은 제약 조건에 적용할 수 있습니다.

위 코드 설명

이 방법에서는 접두사 자릿수를 세어 저장합니다. 이제 우리는 해당 접두사 수를 반복하고 l-1의 비트 수를 제거하여 비트가 임의의 숫자에 설정되어 있는지 알기 때문에 [l, r] 범위에 있는 숫자의 비트 수를 갖도록 쿼리를 계산합니다. 따라서 다른 숫자와 비트 OR을 수행하면 비트는 설정된 상태로 유지되므로 비트 OR의 이 속성을 사용하여 비트 수가 0이 아닌지 확인합니다. 이는 설정된 비트가 있는 범위에 숫자가 있음을 의미하므로 설정합니다. 응답 비트를 선택하고 루프를 계속한 후 마지막으로 응답을 인쇄합니다.

결론

이 기사는 배열이 주어지면 인덱스 범위 [L, R]에서 비트 OR 쿼리를 계산하는 문제를 해결합니다. 우리는 또한 이 문제를 해결하기 위한 C++ 프로그램과 이 문제를 해결하는 완전한 방법(정상적이고 효율적인)을 배웠습니다. C, Java, Python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 기사가 도움이 되었기를 바랍니다.

위 내용은 C++를 사용하여 인덱스 범위 내에서 지정된 배열의 비트별 OR 연산을 쿼리합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!