CF407E k-d-sequence

我们称一组整数序列为好的 $k$-$d$ 序列，是指我们最多可以向序列中插入 $k$ 个数，使得排序后该序列成为公差为 $d$ 的等差数列。 你得到了一个由 $n$ 个整数构成的序列 $a$，你的任务是找到该序列的最长连续子段，使其是一个好的 $k$-$d$ 序列。

第一行包含三个用空格分隔的整数 $n,k,d$（$1 \leq n \leq 2 \cdot 10^{5}$；$0 \leq k \leq 2 \cdot 10^{5}$；$0 \leq d \leq 10^{9}$）。 第二行包含 $n$ 个用空格分隔的整数：$a_{1},a_{2},...,a_{n}$（$-10^{9} \leq a_{i} \leq 10^{9}$）——原始序列。

输出两个用空格分隔的整数 $l$ 和 $r$（$1 \leq l \leq r \leq n$），表示区间 $a_{l},a_{l+1},...,a_{r}$ 是最长的、满足条件的好的 $k$-$d$ 序列的子段。 如果有多个最优答案，输出 $l$ 最小的那一个。

在第一个测试样例中，答案是由数字 2, 8, 6 组成的子段——在加入数字 4 并排序后，序列变为 2, 4, 6, 8，这正是公差为 2 的等差数列。 由 ChatGPT 5 翻译