CF2147I2.Longest Increasing Path (Hard Version)

这是本题的 Hard 版本。不同之处在于本版本的第二个测试点为 $n=300\,000$。本题不允许 Hack。

我们称一个整数序列 $a_1, a_2, \ldots, a_n$ 为距离凸序列（distance-convex），如果对每个 $1 < i < n$，都有 $|a_{i} - a_{i-1}| < |a_{i+1} - a_{i}|$。换句话说，如果你按照 $a_1, a_2, \ldots, a_n$ 的顺序依次跳跃，则每一次跳跃的距离都严格大于上一次。

现在给定两个整数 $n$ 和 $m$。请你找到一个长度为 $n$，且不超过 $m$ 个不同数值的距离凸序列 $a$。从跳跃的角度来看，意味着你要完成 $n-1$ 次递增跳跃，但至多经过 $m$ 个不同的点。对于所有 $1 \leq i \leq n$，需要满足 $-10^{18} \leq a_i \leq 10^{18}$。

输入包含两个整数 $n$ 和 $m$。

本题共两个测试点：

• $n = 8$，$m = 6$；
• $n = 300\,000$，$m = 15\,000$。

保证对于所有测试点都存在解。本题不允许 Hack。

输出一个距离凸序列 $a_1, a_2, \ldots, a_n$，其中最多包含 $m$ 种不同的数值。对于所有 $1 \leq i \leq n$，满足 $-10^{18} \leq a_i \leq 10^{18}$。

如果存在多组解，请输出其中任意一组。

序列 $[1, 1, 3, 6, 10, 3, 11, 1]$ 的长度为 $n=8$，包含 $5$ 个不同的数值，小于等于 $m=6$。相邻元素的差值序列为 $0,2,3,4,7,8,10$，严格递增。

$[1, 1, 2, 4, 8, 16, 32, 1]$ 也是一个合法答案。

由 ChatGPT 5 翻译