HMR的LIS Ⅲ
题目背景
[HMR的LIS Ⅰ](https://www.luogu.org/problemnew/show/T51390)
[HMR的LIS Ⅱ](https://www.luogu.org/problemnew/show/T51391)
在你帮助HMR切掉AKIOI的神仙LSK的两道题后,LSK很不满,决定好好刁难一下你(而不是HMR)
题目描述
LSK又给出了一个长度为n的序列,要求你求出它的IBvl序列
IBvl序列满足以下要求:
1.一个IBvl序列满足$ \forall ~ i \in (1,len] , L < a_i - a_{i-1} < R $,其中$len$为IBvl序列的长度
2.IBvl序列中的元素相对顺序应满足在原序列中的相对顺序
3.在所有满足条件的序列中长度最长
我们视位置不同的元素为不同元素,有任一组成元素不同的IBvl序列为不同IBvl序列
现在要求你输出原序列的IBvl序列的长度,并输出字典序第k小(以元素在原序列中的位置为关键字排序)的序列的每个元素在原序列中的位置
输入输出格式
输入格式
第一行输入4个整数,n,k,L,R
第二行输入n个整数,表示神仙LSK给出的序列
输出格式
第一行输出IBvl序列的长度
第二行输出IBvl序列的每个元素的位置
输入输出样例
输入样例 #1
5 3 2 4
6 8 0 2 7
输出样例 #1
1
3
说明
#### 样例解释:
对于给出的数据,一共有$5$种IBvl序列,分别是:$\{6\},\{8\},\{0\},\{2\},\{7\}$。
他们在原序列中位置的编号序列分别是$\{1\},\{2\},\{3\},\{4\},\{5\}$
IBvl序列的长度为1。
要求输出字典序第$3$小的编号序列,于是输出$3$。
#### 数据范围与约定:
对于20%的数据,$ n \le 18$
对于50%的数据,$ n \le 1000 , | l | , | r | \leq 10^9 , r-l>1 , 0 \le a[i] \le 10^9 $
对于另外10%的数据,$ l=0 , r=10^9+1 , k=1 $
对于另外20%的数据,$ l=0 , r=10^9+1 , k \le 3 $
对于100%的数据,$ n \le 5*10^5 , | l | , | r | \le 10^9 , r-l>1 , k \le 10^{13} , 0 \le a[i] \le 10^9 $
对于所有数据,保证合法且有解。
对于前50%的数据,时限为1s,后50%的数据,时限为2s(~~凉~~良心不卡常)