Codeforces Round #271 (Div. 2) E. Pillars（線段樹優化DP）

題目連結：點選打開連結

題意：一個n個數的序列，每個數有一個高度值h[i]。 求一個最長子序列，要求相鄰兩個數滿足| h[i] - h[i-1] | >= d。 并要求列印出該序列。

類似于最長上升子序列， DP思想很簡單， 但是可惜n太大了， 二重循環會逾時。 是以要想辦法優化掉第二層循環。

觀察發現， 第二層所做的事情就是在所有滿足j<i && | h[i] - h[j] | >= d 的j中找到最大的d[j]。

j < i很容易滿足， 按照順序加入就可以了， 但是還要滿足大小關系， 怎麼辦呢？

把不等式變形就成了： h[j] <= h[i] - d 或者 h[j] >= h[i] + d 。 這不就是一個區間嗎？  是以我們可以以高度為區間建一棵線段樹，由于h[i]太大，先離散化一下。

可見， 線段樹的區間下标并不是沒有用的， 适當利用， 也可以用來維護一些資訊。

細節參見代碼：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int mod = 1000000000 + 7;
const int INF = 1000000000;
const int maxn = 100000 + 10;
int T,m,dd,n,d[maxn],pre[maxn];
ll a[maxn],b[maxn];
struct node {
    int v, id;
}maxv[maxn<<2];
void PushUp(int o) {
    if(maxv[o<<1].v <= maxv[o<<1|1].v) maxv[o] = maxv[o<<1|1];
    else maxv[o] = maxv[o<<1];
}
void build(int l, int r, int o) {
    int m = (l + r) >> 1;
    maxv[o].v = 0;
    if(l == r) return ;
    build(l, m, o<<1);
    build(m+1, r, o<<1|1);
}
void update(int L, int R, int v, int l, int r, int o) {
    int m = (l + r) >> 1;
    if(L <= l && r <= R) {
        if(maxv[o].v < d[v]) {
            maxv[o].v = d[v];
            maxv[o].id = v;
        }
        return ;
    }
    if(L <= m) update(L, R, v, l, m, o<<1);
    if(m < R) update(L, R, v, m+1, r, o<<1|1);
    PushUp(o);
}
node query(int L, int R, int l, int r, int o) {
    int m = (l + r) >> 1;
    if(L <= l && r <= R) {
        return maxv[o];
    }
    node ans ; ans.v = 0;
    if(L <= m) {
        node v = query(L, R, l, m, o<<1);
        if(ans.v < v.v) ans = v;
    }
    if(m < R) {
        node v = query(L, R, m+1, r, o<<1|1);
        if(ans.v < v.v) ans = v;
    }
    PushUp(o);
    return ans;
}
void print(int root) {
    if(d[root] == 0) return ;
    else print(pre[root]);
    if(pre[root] == 0) printf("%d",root);
    else printf(" %d",root);
}
int main() {
        scanf("%d%d",&n,&dd);
        for(int i=1;i<=n;i++) {
            scanf("%I64d",&a[i]);
            b[i] = a[i];
        }
        sort(b+1, b+1+n);
        int m = unique(b+1, b+1+n) - b - 1;
        d[1] = 0;
        build(1, m, 1);
        int ans = 0, root = -1;
        for(int i=1;i<=n;i++) {
            d[i] = 0;
            int L = upper_bound(b+1, b+1+m, a[i] - dd) - b;
            int R = lower_bound(b+1, b+1+m, a[i] + dd) - b;
            L--;
            if(L >= 1) {
                node cur = query(1, L, 1, m, 1);
                if(cur.v + 1 > d[i]) {
                    d[i] = cur.v + 1;
                    pre[i] = cur.id;
                }
            }
            if(R <= m) {
                node cur = query(R, m, 1, m, 1);
                if(cur.v + 1 > d[i]) {
                    d[i] = cur.v + 1;
                    pre[i] = cur.id;
                }
            }
            int v = lower_bound(b+1, b+1+m, a[i]) - b;
            update(v, v, i, 1, m, 1);
            if(ans < d[i]) {
                ans = d[i] ;
                root = i;
            }
        }
        if(ans == 0) { printf("0\n"); return 0; }
        printf("%d\n",ans);
        print(root);
        printf("\n");
    return 0;
}