二進位制陣列中與1進行異或的區間更新查詢

---

介紹

在本教程中，我們將找到一種方法來查詢對二進位制陣列中與1進行異或的區間更新查詢。為了實現這種方法，我們使用一個二進位制陣列，它是一個由0和1組成的陣列。區間更新查詢是指用於修改給定區間上下限內的二進位制陣列的查詢。上下限是二進位制陣列元素的索引。該區間內的元素將使用定義的操作進行更新。

異或是一種位運算，代表“異或”。其基本原理是：如果兩個位相同，則結果為0；如果兩個位不同，則結果為1。

對於給定的區間，我們考慮對二進位制陣列執行與1進行異或的5種類型的區間更新查詢。這5種類型的區間更新查詢如下：

• 查詢二進位制陣列中某個區間的與1進行異或的結果。

• 查詢二進位制陣列中某個區間內與1進行異或的最小距離。

• 查詢二進位制陣列中某個區間內與1進行異或的最大距離。

• 查詢二進位制陣列中某個區間內與0的最小距離。

• 查詢二進位制陣列中某個區間內與0的最小距離。

演示

Input = arr[] = {0,1,0,1,1,0,1}
Query = 5
OUTPUT = 1 3 2 2

解釋

對於輸入的二進位制陣列，使用5個查詢來更新區間[2, 5]。

查詢1 - 對二進位制陣列中區間[2, 5]進行與1的異或運算。

與1進行異或後的二進位制陣列為 {0 1 1 0 0 1 1}。

查詢2 - 計算二進位制陣列中區間[2, 5]內1之間的最小距離。

最小距離為1。

查詢3 - 查詢二進位制陣列中區間[2, 5]內1的最大距離。

最大距離為3。

查詢4 - 查詢二進位制陣列中區間[2, 5]內與0的最小距離。

最小距離為2。

查詢5 - 查詢二進位制陣列中某個區間內與0的最大距離。

最大距離為2。

C++庫函式

• vector - 它是C++中的動態陣列。它在``標頭檔案中定義。向量型別在其宣告期間由其資料型別定義。

vector<data_type> vector_name;

• max() - 它是vector類的預定義函式，在``標頭檔案中定義。它返回兩個值之間的最大距離。

max(value1, value2);

• min() - 它是vector類的預定義函式，在``標頭檔案中定義。它返回兩個值之間的最小距離。

max(value1, value2);

演算法

• 初始化輸入的二進位制陣列。

• 初始化查詢的區間。

• 透過迭代指定的區間來查詢所有5個查詢的輸出。

• 列印所有查詢的結果。

示例

我們在C++中實現了問題陳述。我們為每個查詢建立單獨的使用者定義函式。這些函式使用for迴圈迭代區間，以更新與1進行異或的區間查詢。

#include <bits/stdc++.h>

using namespace std;

int findDistance(const vector<int>& arr, int left, int right, int ans) {
   int d = INT_MAX;
   int ansIdx = -1;

   for (int i = left; i <= right; i++) {
      if (arr[i] == ans) {
         if (ansIdx != -1) {
            d = min(d, i - ansIdx);
         } else {
            ansIdx = i;
         }
      }
   }

   return d;
}

void operation(vector<int>& arr, int left, int right, int o) {
   for (int i = left; i <= right; i++) {
      arr[i] ^= o;
   }
}

int main() {
   vector<int> arr = {0, 1, 0, 1, 1, 0, 1};

   int minDistance1 = findDistance(arr, 2, 5, 1);
   cout << "Min distance between two 1 in range [2, 5]: " << minDistance1 << endl;

   int maxDistance1 = findDistance(arr, 2, 5, 1);
   cout << "Max distance between two 1 in range [2, 5]: " << maxDistance1 << endl;

   int minDistance0 = findDistance(arr, 2, 5, 0);
   cout << "Min distance between two 0 in range [2, 5]: " << minDistance0 << endl;

   int maxDistance0 = findDistance(arr, 2, 5, 0);
   cout << "Max distance between two 0s in range [2, 5]: " << maxDistance0 << endl;

   operation(arr, 2, 5, 1);
   cout << "Array after XOR operation with 1 in range [2, 5]: ";
   for (int num : arr) {
      cout << num << " ";
   }
   cout << endl;
   return 0;
}

輸出

Minimum distance between two elements with 1 in range [2, 5]: 1
Maximum distance between two elements with 1 in range [2, 5]: 1
Minimum distance between two elements with 0 in range [2, 5]: 3
Maximum distance between two elements with 0 in range [2, 5]: 3
Array after XOR operation with 1 for range [2, 5]: 0 1 1 0 0 1 1

結論

我們已經完成了本教程關於區間更新查詢的講解。在這裡，我們實現了在二進位制陣列中查詢與1進行異或的區間更新查詢的問題。使用二進位制陣列實現了C++邏輯來解決問題陳述。我們在定義二進位制陣列元素的區間時，使用了5個區間更新查詢來與1進行異或。對於每個區間更新查詢，使用者定義的函式使用“for”迴圈來迭代索引區間。透過示例演示任務闡述了其含義以及與1進行異或的工作原理。