Hi, I need some help in MINMAGIC problem on Codechef.

The problem statement in short: There are *N* segments, and *Q* queries. Each query is of the form (*A*, *B*). For each segment we need to choose a point on it, say *X* and find *min*(*abs*(*A* - *X*), *abs*(*B* - *X*)). We need to add this *minvalue* for all such segments and report the answer.

What I did: It is easy to find the answer for all segments whose right end point is less than *A* and whose left end point is greater than *B*. The *minvalue* is 0 for intervals that contain either *A* or *B*.

So the problem essentially boils down to this: Given 2 points (*A*, *B*) and some *N* segments all between *A* and *B*. For each segment we either choose its left end point or right end point and find the *minvalue* as above and add it for all the segments.

I don't know how to do this part. I am also not able to understand this solution by I_love_Tanya_Romanova. Also this solution is very clean but still can't understand the last part.

Can anyone help me in this? There are also some solutions by Treaps, I would appreciate if anyone can elaborate on that too.

What if you calculate the median points

M_{i}for every segmentL_{i}-R_{i}and use it as an index in some data structure (maybe Fenwick) for summing stuff? Then, for each query, you calculate the median pointXof the segmentA-Band every segmentithat hasM_{i}> =Xshould be matched withB(i.e.R_{i}should be matched withB); otherwise it should be matched withA(i.e.L_{i}should be matched withA).Just something I came up with... Maybe it's wrong, tell me what you think