**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<sup>th</sup> 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)