碎碎念1：是的时隔两年多笨人又想开始更博客了
碎碎念2：另外今年就要AFO了 希望能给自己的oi生涯画上一个完美的句号！

题目大意

给定\(N\)个数字和\(D\) 需要从中选择一些数字 在保证选中的数字中所有相邻的数字index之差不超过\(D\)的情况下 最大化选中数字的impression score。这里impression score的定义是选中数字中有多少个比前面所有数字都大的数。

题目解法

首先我们关注到贡献到impression score的数字一定组成一个上升子序列，且另外选中的那些不算在impression score的数字只是为了满足index之差不超过\(D\)这个条件的。所以我们可以忽略那些不算在impression score里的数字，从而把这个问题可以被转化成一个类LIS问题，但不同的地方是转移对index也是有要求的。首先我们可以注意到每个数字后面可以接的index范围是可以预处理的。对于一个位置\(i\)，如果我们想接位置\(j\)（我们只考虑上升子序列所以a[\(i\)]<a[\(j\)])，必须保证index在(\(i\), \(j\))这个区间里比a[\(i\)]小的数字没有间隔超过\(D\)的。于是想到一个预处理所有位置可接范围的方法：将所有数字按找从大到小排序，对于每个数字，标记所有大于等于它的位置，然后找到当前数字右边第一个长度为\(D\)的都被标记的连续区间。这个区间的右端点即为当前数字可以接的最大的index。至于怎么维护连续的被mark的区间 我使用了并查集 同时用set存所有长度至少为\(D\)的区间的起点（这里的implementation需要保证每个起点只被试图放进set一次）这样对于每个数字直接在set里面用lower_bound就能找到需要的index（注意+\(D\))。这部分的复杂度是O(\(N\) log \(N\)).
接下来的问题就是怎么快速处理这个类LIS问题。首先注意到这里有点像二维偏序，因此我们可以把所有数字从大到小排序考虑下降子序列，然后用一个线段树存储考虑目前的数字结束在每个位置可以得到的最长下降子序列长度。这样每个位置的答案就是一个线段树上的区间查询。所以我们只需要进行\(N\)次区间查询和单点更新，复杂度为O(\(N\) log \(N\)).