Range Update Queries to XOR with 1 in a Binary Array.

Given a binary array arr[] of size N. The task is to answer Q queries which can be of any one type from below: 
Type 1 – 1 l r : Performs bitwise xor operation on all the array elements from l to r with 1. 
Type 2 – 2 l r : Returns the minimum distance between two elements with value 1 in a subarray [l, r]. 
Type 3 – 3 l r : Returns the maximum distance between two elements with value 1 in a subarray [l, r]. 
Type 4 – 4 l r : Returns the minimum distance between two elements with value 0 in a subarray [l, r]. 
Type 5 – 5 l r : Returns the maximum distance between two elements with value 0 in a subarray [l, r].
Examples: 
 

Input : arr[] = {1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0}, q=5 
Output : 2 2 3 2
Explanation :
query 1 : Type 2, l=3, r=7 
Range 3 to 7 contains { 1, 0, 1, 0, 1 }. 
So, the minimum distance between two elements with value 1 is 2.
query 2 : Type 3, l=2, r=5 
Range 2 to 5 contains { 0, 1, 0, 1 }. 
So, the maximum distance between two elements with value 1 is 2.
query 3 : Type 1, l=1, r=4 
After update array becomes {1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0}
query 4 : Type 4, l=3, r=7 
Range 3 to 7 in updated array contains { 0, 1, 1, 0, 1 }. 
So, the minimum distance between two elements with value 0 is 3.
query 5 : Type 5, l=4, r=9 
Range 4 to 9 contains { 1, 1, 0, 1, 0, 1 }. 
So, the maximum distance between two elements with value 0 is 2.

Approach: 
We will create a segment tree and use range updates with lazy propagation to solve this.

• Each node in the segment tree will have the index of leftmost 1 as well as rightmost 1, leftmost 0 as well as rightmost 0 and integers containing the maximum and minimum distance between any elements with value 1 in a subarray {l, r} as well as the maximum and minimum distance between any elements with value 0 in a subarray {l, r}. 
   
• Now, in this segment tree we can merge left and right nodes as below:

The time and space complexity of the above code is O(1).

• To handle the range update query, we will use lazy propagation. The update query asks us to xor all the elements in the range from l to r with 1, and from observations, we know that :

       0 xor 1 = 1
       1 xor 1 = 0

• Hence, we can observe that after this update all the 0’s will change to 1 and all the 1’s will change to 0. Thus, in our segment tree nodes, all the corresponding values for 0 and 1 will also get swapped i.e.

       l0 and l1 will get swapped
       r0 and r1 will get swapped
       min0 and min1 will get swapped
       max0 and max1 will get swapped

• Then, finally to find the answer to tasks 2, 3, 4 and 5 we just need to call query function for the given range {l, r} and i order to find the answer to task 1 we need to call the range update function.

Below is the implementation of the above approach:
 

2
2
3
2

Time Complexity: O(n*log(n))
Auxiliary Space: O(n)