**Problem Link:**

Contest

Practice

**Author and Editorialist:** sumeet-varma

**Difficulty:** Medium

**Pre-requisites:** - Segment tree

**Problem**: Given *N* intervals*(L[i], R[i])*, you have to minimize the magic for *Q* queries where each query has two parameters *A* and *B* and magic is calculated as follows.

magic = 0

for i in range(0, N)

x = choose any point which lies in i^{th} interval (x ≥ L[i] and x ≤ R[i])

y = choose A or B

magic += |x – y|

**Explanation:**
For a given query *(A <= B)*, intervals having non-zero magic can be split in 3 different categories.

*Case 1: **L[i] <= R[i] <= A*

Case 2: * A < L[i] <= R[i] < B*

Case 3: * B < L[i] <= R[i]*

For case 1, *magic += A - R[i]*. It can be solved in *O(logn)* per query after sorting the intervals on end point and building range sum segment tree/BIT over it. Case 3 can be solved in a similar way.

For case 2,
*Lemma: If (L[i] + R[i]) <= (A + B) , then magic += L[i] - A else magic += B - R[i]*

Proof: Let magic $+= L[i] - A$

$\therefore$ $min(L[i] - A, B - R[i]) = L[i] - A$

$\implies L[i] - A \le B - R[i]$

$\implies L[i] + R[i] \le A + B$

Intuitive Proof: If *midpoint([L[i], R[i]]) $\le$ midpoint([A, B])*, then *L[i]* should be closer to A than *R[i]* is from B.

Thus, we again split the intervals of case 3 in two types.

*Case 3A: A < L[i] <= R[i] < B and L[i] + R[i] <= A + B*

*Case 3B: A < L[i] <= R[i] < B and L[i] + R[i] > A + B*

For case 3A, we **sort the intervals based on ***L[i] + R[i]* and build a segment tree over it in which in each node, we again sort the intervals based on *L[i]* and also build a prefix sum over sorted *L[i]* in each node.

For each query, we find $\sum$ *L[i]* and count of all intervals such that *L[i] > A* and *L[i] + R[i] <= A + B*. We don't need to check for R[i] < B. Think why?

This can be done with the help of binary search on array of sorted intervals for determining prefix of intervals having *L[i] + R[i] <= A + B* and then a range query in segment tree for that prefix.

And finally, *magic += $\sum$ **L[i]* - count * A

Case 3B can be solved in a similar way.

Time Complexity: $O((N + Q) * log^2N)$

Space Complexity: $O(N * log^2N)$