HDU 4521 小明系列问题--小明序列（加强版LIS+线段树单点更新）

题意：

求LIS的长度，但是要求下标之间的差，必须在题目要求范围之内(ij - ij-1 > d)

解析：

利用线段树，查询1~a[i]区间最长子序列的值，并保存dp[i]，当i-d > 0时，将a[i-d-1] 线段树上的值更新为 dp[i-d-1]，并查询1~a[i]区间内的最长子序列。

AC代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#define ls o*2
#define rs o*2+1
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10;
int maxv[N << 2], a[N], dp[N];
int n, d;

int ql, qr;
int query(int o, int L, int R) {
if(ql <= L && R <= qr) return maxv[o];
int M = (L + R)/2, ret = -INF;
if(ql <= M) ret = max(ret, query(ls, L, M));
if(qr > M) ret = max(ret, query(rs, M+1, R));
return ret;
}

int p, v;
void modify(int o, int L, int R) {
if(L == R) {
        maxv[o] = v;
return ;
    }
int M = (L + R)/2;
if(p <= M) modify(ls, L, M);
else modify(rs, M+1, R);
    maxv[o] = max(maxv[ls], maxv[rs]);
}

int main() {
while(scanf("%d%d", &n, &d) != EOF) {
memset(maxv, 0, sizeof(maxv));

int maxn = 0;
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
            maxn = max(maxn, a[i]);
        }

int ans = 0;
for(int i = 1; i <= n; i++) {
if(i - d > 0) { //更新距离 i 为 d 的LIS
                p = a[i-d-1]+1, v = dp[i-d-1];
                modify(1, 1, maxn+1);
            }
if(a[i] > 0) {
                ql = 0, qr = a[i];
                dp[i] = query(1, 1, maxn+1) + 1;
            }else dp[i] = 1;

            ans = max(ans, dp[i]);
        }
printf("%d\n", ans);
    }
return 0;
}