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

时间:2022-04-04 19:33:08

题意:

求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;
}