BZPRO
#4527. K-D-Sequence
内存限制：256 MiB
时间限制：20 Sec
提交
提交记录
讨论
题目描述
我们称一个数列为一个好的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 的等差数列。
数据范围与提示
BZPRO