M 個范圍切換操作后的二進制數組 · GeeksForGeeks 中文系列教程

# M 個范圍切換操作后的二進制數組 > 原文： [https://www.geeksforgeeks.org/binary-array-m-range-toggle-operations/](https://www.geeksforgeeks.org/binary-array-m-range-toggle-operations/) 考慮由 N 個元素組成的二進制數組（最初所有元素均為 0）。之后，您將獲得 M 條命令，其中每條命令的形式均為 b，這意味著您必須將 a 到 b 范圍內的所有數組元素都進行切換（包括兩端）。執行完所有 M 條命令后，您必須找到結果數組。 **示例**： ``` Input : N = 5, M = 3 C1 = 1 3, C2 = 4 5, C3 = 1 4 Output : Resultant array = {0, 0, 0, 0, 1} Explanation : Initial array : {0, 0, 0, 0, 0} After first toggle : {1, 1, 1, 0, 0} After second toggle : {1, 1, 1, 1, 1} After third toggle : {0, 0, 0, 0, 1} Input : N = 5, M = 5 C1 = 1 5, C2 = 1 5, C3 = 1 5, C4 = 1 5, C5 = 1 5 Output : Resultant array = {1, 1, 1, 1, 1} ``` **樸素的方法**：對于給定的 N，我們應該創建一個 n + 1 個元素的布爾數組，對于 M 個命令中的每一個，我們都必須從 a 迭代到 b，并借助 a 來切換 a 到 b 范圍內的所有元素 XOR。此方法的復雜度為 O（n ^ 2）。 ``` for (int i = 1; i > a >> b; for (int j = a; j <= b; j++) arr[j] ^= 1; ``` **高效方法**：該思想基于[前綴和數組文章](https://www.geeksforgeeks.org/prefix-sum-array-implementation-applications-competitive-programming/)中討論的樣本問題。對于給定的 n，我們創建 n + 2 元素的布爾數組，對于 M 條命令中的每條命令，我們僅需借助 XOR 切換元素 a 和 b + 1。在所有命令之后，我們將數組處理為 arr [i] ^ = arr [i-1]; 此方法的復雜度為`O(n)`。 ## C++ ```cpp // CPP program to find modified array after? // m range toggle operations. #include<bits/stdc++.h> using namespace std; // function for toggle void command(bool arr[], int a, int b) { ????arr[a] ^= 1; ????arr[b+1] ^= 1; } // function for final processing of array void process(bool arr[], int n) { ????for (int k=1; k<=n; k++) ????????arr[k] ^= arr[k-1]; } // function for printing result void result(bool arr[], int n) { ????for (int k=1; k<=n; k++) ????????cout << arr[k] <<" "; } // driver program int main() { ????int n = 5, m = 3; ????bool arr[n+2] = {0}; ????// function call for toggle ????command(arr, 1, 5); ????command(arr, 2, 5); ????command(arr, 3, 5); ????// process array ????process(arr, n); ????// print result ????result(arr, n); ????return 0; }? ``` ## Java ```java // Java program to find modified array? // after m range toggle operations.? class GFG { // function for toggle? static void command(boolean arr[],? ????????????????????int a, int b) { ????arr[a] ^= true; ????arr[b + 1] ^= true; } // function for final processing of array? static void process(boolean arr[], int n)? { ????for (int k = 1; k <= n; k++)? ????{ ????????arr[k] ^= arr[k - 1]; ????} } // function for printing result? static void result(boolean arr[], int n)? { ????for (int k = 1; k <= n; k++)? ????{ ????????if(arr[k] == true) ????????????System.out.print("1" + " "); ????????else ????????????System.out.print("0" + " "); ????} } // Driver Code public static void main(String args[]) { ????int n = 5, m = 3; ????boolean arr[] = new boolean[n + 2]; ????// function call for toggle? ????command(arr, 1, 5); ????command(arr, 2, 5); ????command(arr, 3, 5); ????// process array? ????process(arr, n); ????// print result? ????result(arr, n); } } // This code is contributed? // by PrinciRaj1992 ``` ## Python3 ```py # Python 3 program to find modified array after? # m range toggle operations. # function for toggle def command(brr, a, b): ????arr[a] ^= 1 ????arr[b+1] ^= 1 # function for final processing of array def process(arr, n): ????for k in range(1, n + 1, 1): ????????arr[k] ^= arr[k - 1] # function for printing result def result(arr, n): ????for k in range(1, n + 1, 1): ????????print(arr[k], end = " ") # Driver Code if __name__ == '__main__': ????n = 5 ????m = 3 ????arr = [0 for i in range(n+2)] ????# function call for toggle ????command(arr, 1, 5) ????command(arr, 2, 5) ????command(arr, 3, 5) ????# process array ????process(arr, n) ????# print result ????result(arr, n) # This code is contributed by # Surendra_Gangwar ``` ## C# ```cs // C# program to find modified array? // after m range toggle operations.? using System; class GFG { // function for toggle? static void command(bool[] arr,? ????????????????????int a, int b) { ????arr[a] ^= true; ????arr[b + 1] ^= true; } // function for final processing of array? static void process(bool[] arr, int n)? { ????for (int k = 1; k <= n; k++)? ????{ ????????arr[k] ^= arr[k - 1]; ????} } // function for printing result? static void result(bool[] arr, int n)? { ????for (int k = 1; k <= n; k++)? ????{ ????????if(arr[k] == true) ????????????Console.Write("1" + " "); ????????else ????????????Console.Write("0" + " "); ????} } // Driver Code public static void Main() { ????int n = 5, m = 3; ????bool[] arr = new bool[n + 2]; ????// function call for toggle? ????command(arr, 1, 5); ????command(arr, 2, 5); ????command(arr, 3, 5); ????// process array? ????process(arr, n); ????// print result? ????result(arr, n); } } // This code is contributed? // by Akanksha Rai ``` ## PHP ```php <?php // PHP program to find modified array? // after m range toggle operations.? // function for toggle? function command($arr, $a, $b)? { ????$arr[$a] = $arr[$a] ^ 1; ????$arr[$b + 1] ^= 1; } // function for final processing? // of array? function process($arr, $n)? { ????for ($k = 1; $k <= $n; $k++)? ????{ ????????$arr[$k] = $arr[$k] ^ $arr[$k - 1]; ????} } // function for printing result? function result($arr, $n)? { ????for ($k = 1; $k <= $n; $k++)? ????echo $arr[$k] . " "; } // Driver Code $n = 5; $m = 3; $arr = new SplFixedArray(7); $arr[6] = array(0); // function call for toggle? command($arr, 1, 5); command($arr, 2, 5); command($arr, 3, 5); // process array? process($arr, $n); // print result? result($arr, $n); // This code is contributed? // by Mukul Singh ?> ``` **輸出**： ``` 1 0 1 1 1 ``` 本文由 [**Shivam Pradhan（anuj_charm）**](http://www.facebook.com/ma5ter6it) 提供。如果您喜歡 GeeksforGeeks 并希望做出貢獻，您還可以使用 [tribution.geeksforgeeks.org](http://www.contribute.geeksforgeeks.org) 撰寫文章，或將您的文章郵寄至 tribution@geeksforgeeks.org。查看您的文章出現在 GeeksforGeeks 主頁上，并幫助其他 Geeks。