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
", ans);
    }
    return 0;
}