C++를 사용하여 다음을 중국어로 번역합니다. 주어진 배열의 인덱스 범위 내에서 비트 AND 쿼리

이 기사에서는 주어진 정수 배열에서 주어진 범위(예: 7minus)의 비트별 AND를 찾는 문제가 제공됩니다. 먼저 무차별 대입 방법을 적용하고 시간 복잡도를 확인합니다. 시간 복잡도가 충분하지 않으면 더 나은 방법을 개발하려고 노력합니다.

Brute Force Method

주어진 방법에서 우리는 주어진 범위를 반복하고 우리의 방법에 대한 답을 찾아서 인쇄할 것입니다.

Example

Input: arr[ ] = {1, 3, 1, 2, 32, 3, 3, 4, 4}, q[ ] = {{0, 1}, {3, 5}}
Output:
1
0 0
1 AND 31 = 1
23 AND 34 AND 4 = 00
Input: arr[ ] = {1, 2, 3, 4, 510, 10 , 12, 16, 8}, q[ ] = {{0, 42}, {1, 33, 4}}
Output:
0 8
0

Output

#include <bits/stdc++.h>
using namespace std;
int main() {
   int ARR[] = { 10, 10 , 12, 16, 8 };
   int n = sizeof(ARR) / sizeof(int); // size of our array
   int queries[][2] = { {0, 2}, {3, 4} }; // 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 = 1LL << 32;
      ans -= 1; // making all the bits of ans 1
      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;
}

이 접근 방식에서는 쿼리의 각 범위에 대해 루프를 실행하고 해당 세트를 비트 단위로 인쇄하므로 프로그램의 전체 복잡성은

O(N*Q )

가 됩니다. 여기서 N은 배열의 크기와 Q는 현재 우리가 가지고 있는 쿼리의 수입니다. 이러한 복잡성이 더 높은 제약 조건에 적합하지 않다는 것을 알 수 있으므로 이 문제에 대한 더 빠른 방법을 제시할 것입니다. 효율적인 방법

이 문제에서는 배열의 접두사 비트 수를 미리 계산하고 주어진 범위에서 설정된 비트의 기여도를 확인하여 주어진 범위의 비트 AND를 계산합니다.

예제

8
0

출력

#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 == r - l + 1)
         ans = ans | 1LL << i;
      }
   return ans;
}
int main() {
   int ARR[] = { 10, 10 , 12, 16, 8 };
   int n = sizeof(ARR) / sizeof(int); // size of our array
   memset(prefixbits, 0, sizeof(prefixbits)); // initializing all the elements with 0
   bitcount(ARR, n);
   int queries[][2] = {{0, 2}, {3, 4}}; // 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;
}

이 접근 방식에서는 상수 시간을 사용하여 쿼리를 계산하므로 시간 복잡도가

O(N*Q)

에서 O(N)(여기서 N은 현재)로 크게 줄어듭니다. 주어진 배열의 크기. 이 절차는 더 높은 제약 조건에도 적용할 수 있습니다. 위 코드 설명

이 방법에서는 모든 접두사 숫자를 계산하여 인덱스에 저장합니다. 이제 쿼리를 계산할 때 특정 비트의 개수가 범위에 있는 요소의 개수와 같은지 확인하면 됩니다. 그렇다면 x에서 이 비트를 1로 설정하고, 그렇지 않으면 주어진 범위에 존재하는 숫자에 해당 비트가 0인 것처럼 비트를 그대로 두므로 해당 비트의 전체 비트 AND가 0이 됩니다. 비트 AND를 계산합니다.

결론

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

위 내용은 C++를 사용하여 다음을 중국어로 번역합니다. 주어진 배열의 인덱스 범위 내에서 비트 AND 쿼리의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!