GOOGOL06 – ACM vs CSES PROBLEM STATEMENT: Practice, Contest CATEGORY: HARD PREREQUISITES: Segment trees, Lazy propagation, Properties of XOR EXPLAINATION: To understand the range update query we have to think how to use properties of XOR to get a result. Let us consider a simpler version of the problem. Let n be the number of elements in the range. Now if I want to invert all the elements in the range then, there are two cases: But in the question it is asked to invert only the alternate elements. The basic idea remains the same, i.e. if the number of elements to be inverted is even then no change otherwise we have to invert the XOR (another solution can be to store the XOR of alternate elements separately and perform the operation mentioned above and then recalculate the overall XOR). It is quite trivial to find the number of elements going to be inverted in a given range. We have missed one point here i.e. since the query asks us to update alternate elements in the range, two cases can occur when we divide the range to move down in the segment tree: To understand it clearly, let the range is [1, 5] and we want to update [2, 4] (which implies we need to update element 2 and element 4), and the division of range [1, 5] occurs in [1, 3] and [4, 5] (child nodes), then the range [2, 4] is divided in to [2, 3] and [4, 4] both of which require inversion as mentioned in Case 1. If the division of range [1, 5] is [1, 2] and [3, 5] then [2, 4] is divided into [2, 2] and [3, 4]. Here, [2, 2] requires an inversion of Case 1 and [3, 4] requires an inversion of Case 2. Depending upon the case we have different number of elements to be inverted in a range. Since, there are now two cases of range update we need to find a way such that if both of the update come together on a node we have to deal it there only and not propagate it ahead (If you make the code such that it propagates the one of the above updates if the other one comes to a node then it will result in TLE. Why? Think yourself). This can be done by considering another state which implies that both 1 and 2 updates are present on this node. To understand it better see the propagate function in the code. C++ CODE: Author: Naman Taneja asked 21 May '15, 17:27
