C++ を使用して、次を中国語に翻訳します: 指定された配列のインデックス範囲内のビット単位の AND をクエリします。

この記事では、整数の配列が与えられた場合、与えられた範囲のビットごとの AND を見つけることがタスクとして与えられます (例: 7minus;

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

)。まず総当たり法を適用して、その時間計算量を確認します。時間計算量が十分でない場合は、より良い方法の開発を試みます。

ブルート フォース メソッド

指定されたメソッドで、指定された範囲を反復処理し、メソッドの答えを見つけて出力します。

例

#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;
}

出力

8
0

このアプローチでは、クエリの各範囲でループを実行し、それらのセットをビットごとに出力するため、プログラム全体の複雑さは ## になります。 #O(N*Q)、ここで、N は配列のサイズ、Q は現在のクエリの数です。この複雑さは、より高い制約には適さないことがわかります。この問題の解決方法。

効率的な方法

この問題では、配列の接頭辞の桁数を事前に計算し、指定された範囲の設定ビットの寄与をチェックすることによって、指定された範囲のビットごとの AND を計算します。範囲。

例

#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;
}

出力

2
0

このアプローチでは、定数時間を使用してクエリを計算し、時間の複雑さを

O(N* Q)## から削減します。 # は O(N) に大幅に縮小されます。ここで、N は指定された配列のサイズです。この手順は、より高度な制約にも適応できます。 上記コードの説明

このメソッドでは、すべての接頭辞の桁をカウントし、インデックスに格納します。ここで、クエリを計算するときは、特定のビットの数が範囲内に存在する要素の数と同じかどうかを確認するだけで済みます。 「はい」の場合、このビットを x の 1 に設定します。「いいえ」の場合、指定された範囲内に存在する数値のビットが 0 であるかのようにビットをそのままにし、そのビットのビットごとの AND 全体がゼロになります。これが私たちのやり方です。ビット単位の AND を計算します。

結論

この記事では、大規模なバッチにわたって、指定されたインデックス範囲 [L, R] でビット単位の AND 演算されたすべてのクエリを列挙するという問題を解決しました。また、この問題を解決する C プログラムと、この問題を解決する完全な方法 (通常かつ効率的) も学びました。同じプログラムを C、Java、Python などの他の言語で書くことができます。この記事がお役に立てば幸いです。

以上がC++ を使用して、次を中国語に翻訳します: 指定された配列のインデックス範囲内のビット単位の AND をクエリします。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。