CF1661D Progressions Covering

给定两个数组：一个长度为 $n$ 的数组 $a$，初始时所有元素均为 $0$，以及一个长度为 $n$ 的数组 $b$，其中包含 $n$ 个整数。 你可以对数组 $a$ 进行如下操作任意次：选择 $a$ 的一个长度为 $k$ 的子段，并在该子段上加上等差数列 $1, 2, \ldots, k$，即对子段的第一个元素加 $1$，第二个元素加 $2$，依此类推。所选子段必须完全位于数组 $a$ 的范围内（即如果子段左端点为 $l$，则需满足 $1 \le l \le l + k - 1 \le n$）。注意，每次加的等差数列始终为 $1, 2, \ldots, k$，而不是 $k, k-1, \ldots, 1$ 或其他形式（即子段最左边的元素总是加 $1$，第二个元素加 $2$，以此类推）。 你的任务是求出使得对每个 $i$（$1 \le i \le n$）都有 $a_i \ge b_i$ 所需的最小操作次数。注意，所有元素都必须同时满足 $a_i \ge b_i$。

输入的第一行包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 3 \times 10^5$），分别表示数组的长度和子段的长度。 第二行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$1 \le b_i \le 10^{12}$），其中 $b_i$ 表示数组 $b$ 的第 $i$ 个元素。

输出一个整数，表示满足 $a_i \ge b_i$ 的最小操作次数。

考虑第一个样例。在这个测试中，我们实际上没有选择的余地，必须至少加 $5$ 次等差数列，才能使第一个元素等于 $5$。此时数组 $a$ 变为 $[5, 10, 15]$。 再看第二个样例。我们可以在区间 $[1, 3]$ 上加一次等差数列，在区间 $[4, 6]$ 上加两次等差数列。此时数组 $a$ 变为 $[1, 2, 3, 2, 4, 6]$。 由 ChatGPT 4.1 翻译