Codeforces 1060G. Balls and Pockets

题意

有一个从 $0$ 到 $\infty$ 的序列，第 $a_1,a_2,\dotsc,a_n$ 个位置上各有一个口袋

每秒每个口袋会吃掉当前位置上的数，较大的数会向较小的方向移动以填补空位

$m$ 次询问在 $k_i$ 秒后一个位置 $x_i$ 上的数是什么

$a_1< a_2< \cdots< a_n$

$n,m\le 10^5, a_i,k_i,x_i\le 10^9$

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}$