Difficulty : MediumHard Time Complexity : O( N√N + Q ) Now, we start processing the segments as in MO’s. These segments are numbered say 1 to n. Maintain a vector<int> 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”.
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 : (41)+(106) . 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 asked 12 Feb '18, 15:56

How come this solution https://www.codechef.com/viewsolution/17408003 that uses a bitset of total size 10^10 bits (i.e. 1250 MBs) passed, where normally memory limit is 256 MB or 512 MB in long challenge questions. Also, the memory limit is not mentioned at all in the problem. This solution solves the problem without any segment tree or sqrt decomposition but just using bitsets. I think this kind of solutions having O(N^2) memory are not supposed to pass. @admin @markysha answered 12 Feb '18, 16:01
1
(12 Feb '18, 16:05)
Ohk i think u didnt caught my solution. Here it is: https://www.codechef.com/viewsolution/17370522 It passed as i think there were some weak test cases (but not very weak)
(12 Feb '18, 16:10)

Really Good editorial @kaushal101. (A bit late to review, I am i guess). answered 14 Feb '18, 00:05

Hey, thanks for the editorial, I understood your clever solution, but when I tried to implement it, I am getting segmentation fault for some reason, if it's not too much trouble can you look into the code once? https://www.codechef.com/viewsolution/17434674 thanks in advance. Edit: I got it, I had done a trivial mistake. Thanks for the editorial. answered 13 Feb '18, 19:06

Assume a scenario where 1.For each query sort the points that gives O(mlogm) 2.For Each Interval do a binary search over that gives overall O(Nlogm) 3.Total Runtime is O((m+n)logm)) Please correct my analysis if i am wrong This approach gave TLE why?? Thanks in Advance code: https://www.codechef.com/viewsolution/17249574 answered 14 Feb '18, 01:05
1
You are doing binary search for each query over each segment. That makes it O(NQlog(m)). Hence TLE :(
(14 Feb '18, 15:36)

@kaushal101 can you please explain how the last part of your code is calculating the answer for each query? "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 : (41)+(106) . We do this for each query, ans[i] will hold the list of seg nos for a query." I read it many times but still I'm confused! answered 17 Feb '18, 13:53

on what i learnt from Mo's algorithm,i implemented this... getting SIGSEGV and TLE .. Surely something is wrong with my approach... Could anyone care to point it out.. my solution https://www.codechef.com/viewsolution/17485189 answered 19 Feb '18, 14:25
First of all, ur comp () fn is wrong: It must be: bool comp(node a,node b) {
} Doing this runs the 1st subtask. Now, u are applying MO's for each query qhich is giving TLE. Preprocess all the query points, and apply MO's only once.
(24 Feb '18, 10:50)
