Difficulty : Medium-Hard
Prerequisite : MO’s Algorithm.
Problem : Given N segments of form Li,Ri. Q queries, each query Qi containing Mi no of points. For each query give the count of the no of segments which hold odd no of points.
Time Complexity : O( N√N + Q )
Approach : For each point between 1 and 10^6, we maintain a list of queries it comes from in vector pnt[10^6+1]. Now we apply MO’s algorithm on the given N segments. Follow this link for MO’s Algo . First we sort the segments based on block number of L values, then in each block, the segments are sorted wrt R values.
Now, we start processing the segments as in MO’s. These segments are numbered say 1 to n. Maintain a vector ans[q]; Now for each point that is being processed, we scan the list of queries it comes from which is already stored in pnt. Now in each of these queries, we check if the current segment number is already pushed, then we pop it off, else we push the current segment number. In a way it implies that if odd number of points from that query are lying in the current segment, the segment number is pushed. Now if we get one more point, it makes the point count even, so we pop it off. Now for the next segment, we have to shift our current l and r pointers. We do the same thing here as well, i.e. while processing these points, if we get odd points, we will push this segment number, else pop.
Now, since we have carried forward from our previously processed segment, then say for a query q1 if we haven’t pushed this current segment no and the previous segment no was pushed, it implies that the change in the no of points while shifting l and r pointers was even, which in turn implies that the current segment also contains odd+even= “odd” no of points in q1. On the other hand if current segment number is pushed, it implies that the points are now odd+odd= “even”.
So now for a query q1 say, the following segment numbers are pushed : 1,4,6 and total no of segment numbers is say 10;
Then it implies that for segment nos 1 to 3,the count was odd. At seg 4, count switched to even,so from seg no 4 to 5,count was even. The count again switched to odd at 6, so from 6 to 10, the count will stay odd. Since we have to only find the odd count, we sum the difference between every two alternate segment nos. As of here, the count is : (4-1)+(10-6) .
We do this for each query, ans[i] will hold the list of seg nos for a query.
Link to my code.https://www.codechef.com/viewsolution/17385662
Please comment below if you have any doubt, or a better solution.