この記事では、整数の配列が与えられています。私たちのタスクは、指定された範囲内のすべての数値のビット単位の 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
)。指定された問題では、ブルート フォース アプローチを使用してそれを解決し、それがより高い制約に適用できるかどうかを確認します。 。そうでない場合は、より高い制約に適合するように方法を最適化します。
このメソッドでは、各範囲を反復処理し、その範囲内のすべての数値のビット単位の OR を計算し、答えを出力します。
#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; }
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 ではないかどうかを確認します。これは、設定された bit の範囲内に数値があることを意味します。答えビットを入力してループを継続し、最後に答えを出力します。
この記事では、配列を指定してインデックス範囲 [L, R] でビットごとの OR クエリを計算する問題を解決します。また、この問題を解決する C プログラムと、この問題を解決する完全な方法 (通常かつ効率的) も学びました。同じプログラムを C、Java、Python などの他の言語で書くことができます。この記事がお役に立てば幸いです。
以上がC++ を使用して、インデックス範囲内の指定された配列のビットごとの OR 演算をクエリします。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。