「Codeforces 1034D」Intervals of Intervals

zx2003说多 log 过不去,不然就去写了

Codeforces 1034D

题意

你有 \(n\) 个区间 \([a_i, b_i]\),定义区间的区间 \([l,r]\) 的价值是第 \(l\) 个区间到第 \(r\) 个区间的并的总长度

你需要找出 \(k\) 个不同的区间的区间,使得它们的总价值最大

输出总价值

\(1\le n \le 3 * 10^5,1 \le k \le \min\{\frac{n(n+1)}{2},10^9\}\)

Read more