GOOGOL06 – ACM vs CSES
PROBLEM STATEMENT: Practice, Contest
CATEGORY: HARD
PRE-REQUISITES: Segment trees, Lazy propagation, Properties of XOR
EXPLAINATION:
The problem was to produce result to some of the queries. The constraints required each query to be solved in log(n) time. Queries of the type A and C were simple point update and point query respectively. Query of type D was a simple range query which can also be done easily. The only problem is query of type B which is a range update query (for which you’ll have to use lazy propagation).
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:
1. If n is even then no change in the XOR of all the elements in the range.
2. If n is odd then the XOR of all the elements becomes bitwise not of the previous XOR of the range.
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:
1. The element inversion starts with the 1st (or say 0th) element.
2. The element inversion starts with the 2nd (or say 1st) element.
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:
Link
Author: Naman Taneja
Tester: Prayank Mathur
Editorialist: Naman Taneja