PROBLEM LINK:Author: Hasan Jaddouh DIFFICULTY:Medium PREREQUISITES:Segment Trees PROBLEM:Given is an array $A$ of length $N$. There are two types of operations that we need to handle on this array:
EXPLANATION:The nature of the problem clearly hints towards segment trees. We need to efficiently perform the bitwiseAnd operation over a range of numbers and then report the minimum. Reporting the minimum is a standard operation with segment trees: we just have to store the minimum for the corresponding range at each node of the segment tree, and we can answer the queries in $\mathcal{O}(\log N)$ time. But how do we update the minimums when an update operation is requested? There are no such apparent properties of bitwiseAnd operation that can be applied to a range. There isn't a notion of an elegant lazy propagation either since we need to perform rangeupdate and rangeminimum query. But there is one nice property that we can observe about our update operation: if in a particular update operation, we have an $x$ such that its $i^{th}$ bit (rightmost bit is $0^{th}$ bit) is 0, then the $i^{th}$ bit of all the numbers in the range to be updated becomes 0; and for the rest of the execution of our program, remains 0. This is because there is no way to turn a 0 bit to 1 using bitwiseAnd operations only. This gives us a huge hint about an efficient algorithm that we can use. It tells us that we are only interested in the those bits of $x$ which are 0, because the 1 bits are not going to change anything. Furthermore, for a particular node in the segment tree, if we know that there exists no number within its range of indexes such that some bit in that number is 1 while the same bit is 0 in $x$, then we don't need to bother updating it or its descendants because again nothing is going to change. So now we know how to build our segment tree, i.e., what information to store in each of its node. Each node of the segment tree will have a boolean array named $bits$ of length 32 and an integer $mini$. In the array $bits$, $bits[i]$ = true indicates that there is at least one number in the range represented by the node such that its $i^{th}$ bit is 1. Accordingly, if it is false then there is no number within the range of the node such that its $i^{th}$ bit is 1. The integer $mini$ represents the minimum of all the numbers within the range of the node. So we now have a way to initialise our segment tree. It is given below as pseudocode:
The update function is very similar, except that we impose the condition that we discussed earlier. If a node $r$ falls within the range to be updated, we will recurse down to update its descendents if and only if there exists an $i$ such that the $i^{th}$ bit in $x$ is 0 but $segTree[r].bits[i]$ is 1. If during update, we reach a leaf node, we simply do $segTree[leaf].mini$ = bitwiseAnd($segTree[leaf].mini$, $x$). The query operation is a standard rangeminimum query operation which can be performed with the help of the stored $mini$ values. If the reader doesn't know about it then he/she can refer here rangemin query using segment trees. What is the complexity of our approach? If we look closely, each bit in each number of the array can only set to 0 once. Reaching a number, i.e., reaching a leaf takes $\mathcal{O}(\log N)$ time in a segment tree. Since there are $\log A_{max}$ bits at maximum in any number within the given array $A$, therefore, it will take $\mathcal{O}(\log A_{max})$ per number to set its bits to 0. Since there are $N$ numbers in total, thus, the net complexity is $\mathcal{O}(N\log N\log A_{max})$ per test case. Please see editorialist's/setter's program for implementation details. COMPLEXITY:$\mathcal{O}(N\cdot\log N\cdot\log A_{max})$ per test case. SAMPLE SOLUTIONS:
This question is marked "community wiki".
asked 21 Jun '16, 03:07

I tried it do with lazy propogation, but got WA( and I am not able to find the bug). Here's the link to my code> https://www.codechef.com/viewsolution/10624668. answered 27 Jun '16, 09:46

@sandeep9 . At an intuitive level as it looks , we cant use lazy propagation ! because the moment you update a range with lazy, you need to update the min value ( i.e our solution for the node) at that very moment . But theres no simple way to do so . suppose theres a node [L,R] with min value A and while updating the solution of this node , you mark it as lazy and update A with A=A&X . This is the thing which is going wrong . Theres no certainty that new solution will be A&X . EXAMPLE : let the node [L,R] contain values {1,2,3,8} , solution for this node is 1 . now an update query comes with X=7 over [L,R] , now according to the lazy solution the answer will be 1&7= 1. but actually 8&7 = 0 . so our answer should be 0 but you take it as 1. hope you are getting it ! answered 27 Jun '16, 13:19

@pushkarmishra . We can keep two values in your structure :
Now we can update the tree in the building the tree fashion and neglect a range if X&Bor==Bor . quite similar to the editorial though. answered 27 Jun '16, 13:41

Source limit is being given in almost every problem as 50000 Bytes.. What does it mean..?? In this problem.. The N could be atmost (10^5)... so, if we declare an integer array of size 10^5.. then (10^5)*2 = 200000 Bytes are required.. but source limit is given as only 50000 Bytes.. What does it mean?? please explain me this.. answered 26 Jul '16, 10:28
