Intervals of Intervals
Contest: Codeforces Round 511 (Div. 1)
Difficulty rating: 3500
Tags: binary search, data structures, two pointers

Little D is a friend of Little C who loves intervals very much instead of number "$$$3$$$".

Now he has $$$n$$$ intervals on the number axis, the $$$i$$$-th of which is $$$[a_i,b_i]$$$.

Only the $$$n$$$ intervals can not satisfy him. He defines the value of an interval of intervals $$$[l,r]$$$ ($$$1 \leq l \leq r \leq n$$$, $$$l$$$ and $$$r$$$ are both integers) as the total length of the union of intervals from the $$$l$$$-th to the $$$r$$$-th.

He wants to select exactly $$$k$$$ different intervals of intervals such that the sum of their values is maximal. Please help him calculate the maximal sum.

Input format:
First line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 3 \cdot 10^5$$$, $$$1 \leq k \leq \min\{\frac{n(n+1)}{2},10^9\}$$$) — the number of intervals Little D has and the number of intervals of intervals he will select.

Each of the next $$$n$$$ lines contains two integers $$$a_i$$$ and $$$b_i$$$, the $$$i$$$-th line of the $$$n$$$ lines describing the $$$i$$$-th interval ($$$1 \leq a_i < b_i \leq 10^9$$$).

Output format:
Print one integer — the maximal sum of values Little D can get.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
For the first example, Little D will select $$$[1,2]$$$, the union of the first interval and the second interval is $$$[1,4]$$$, whose length is $$$3$$$.

For the second example, Little D will select $$$[1,2]$$$, $$$[2,3]$$$ and $$$[1,3]$$$, the answer is $$$5+6+4=15$$$.

Example input:
2 1
1 3
2 4

Example output:
3

Example input:
3 3
1 4
5 7
3 6

Example output:
15

Editorial:
First we consider how to calculate the value of an interval of intervals $$$[l,r]$$$. We can consider intervals in order from $$$1$$$ to $$$n$$$ and, for each position on the axis, maintain a timestamp denoting the last time it was covered. When the $$$r$$$-th interval is taken into consideration, the timestamps for positions $$$[a_r, b_r]$$$ should all be updated to $$$r$$$. Right after that, the desired answer of a query $$$[l,r]$$$ is the number of positions whose timestamp is not smaller than $$$l$$$.
We would like to, for each $$$r$$$, keep the desired answer for every $$$l$$$. To achieve this, when we change the timestamps of $$$k$$$ positions from $$$r'$$$ to $$$r$$$, the answers for $$$l$$$ in $$$[r'+1,r]$$$ should each be increased by $$$k$$$.
To do it fast, we can merge consecutive positions with the same timestamp into a segment, and use a balanced tree (e.g. std::set) to maintain the segments. $$$O(1)$$$ new segments appear when adding an interval, and when a segment is completely covered by later intervals, it will be deleted. By amortized analysis, the total number of balanced tree operations and the number of range modifications of answers (see above) are both $$$O(n)$$$. We spend $$$O(n \log n)$$$ time in this part.
Now we consider how to get the answer. It's obvious that we will select the $$$k$$$ largest values. We can use binary search to find the minimum we finally select, i.e. we should, for several intergers $$$x$$$, count how many values of $$$[l,r]$$$ are not smaller than $$$x$$$ and count the sum of these values by the way to get the answer.
For each $$$i$$$, we will select all $$$[l,i]$$$'s such that their interval of intervals values is not smaller than $$$x$$$. It's obvious that all $$$l$$$'s smaller than an integer $$$L_i$$$ will be taken. As the value of $$$[l,r]$$$ is not smaller than $$$[l+1,r]$$$ or $$$[l,r-1]$$$, $$$L_{i+1}$$$ will be not smaller than $$$L_i$$$. Now we can iterate $$$i$$$ from $$$1$$$ to $$$n$$$, maintaining the sum of values of $$$[l,i]$$$ ($$$1 \leq l < L_i$$$) and the value of $$$[L_i,i]$$$ by maintaining the difference between the answers for $$$l$$$ and $$$l+1$$$ (in this way we carry out a range increment in $$$O(1)$$$ time). Similar to the sliding-window method, we try to increase $$$L_i$$$ when $$$i$$$ changes to $$$i+1$$$. Therefore, we spend $$$O(n)$$$ time for each $$$x$$$ we check with.
Summing everything up, the total time complexity of this problem is $$$O(n \ (\log n+\log \max b))$$$.