8527: BZOJ4527：K-D-Sequence

我们称一个数列为一个好的k-d数列，当且仅当我们在其中加上最多k个 数之后，数列排序后为一个公差为d的等差数列。 你手上有一个由n个整数组成的数列a。你的任务是找到它的最长连续子 串，使得满足子串为好的k-d数列。

输入格式

第一行包含三个用空格隔开的整数n,k,d（1<=n<=2*10^5;0<=k<= 2*10^5;0<=d<=10^9）。第二行包含n个空格隔开的整数：a1,a2,...,an（-10^9<=ai<=10^9）表示数列a。

输出格式

输出两个用空格隔开的整数L,r（1<=L<=r<=n），表示数列a_L,a_L+1,..., ar是好k-d数列的子串中最长的。 如果有多个最优答案，输出那个L值最小的。

样例输入

6 1 2
4 3 2 8 6 2

样例输出

3 5
//第一个测试样例的答案为包括数字 2，8，6 的子串——在加入数字 4 并且
排序之后，它变成了数列 2，4，6，8——公差为 2 的等差数列。

提示

没有写明提示

题目来源

没有写明来源