标签: 单调队列

1 篇文章

Luogu – P3509 – [POI2010]ZAB-Frog
数轴上有 $n$ 个点,坐标分别为 $p_1, p_2, \cdots, p_n$ 在这些点上按照某些规则跳。
规则是:每次向距当前点第 $k$ 小的点跳,如果有相同距离则向下标较小的跳;
求从每个点出发跳了 $m$ 次后在哪里.
$1\leq k < n\leq 10^6, 1\leq m\leq 10^{18}, 1\leq p_i\leq 10^{18}$.