题目：给出一个序列，找出一个最长的子序列，相邻的两个数的差在d以内。
1 /* 2 线段树优化dp 3 dp[i]表示前i个数的最长为多少，则dp[i]=max(dp[j]+1) abs(a[i]-a[j])<=d 4 复杂度为O(n ^ 2) 5 利用线段树优化，线段树保存区间最大值。离散化后便可求出，还要注意 对于叶子节点保存的即为dp的值，每次更改即可，开始一直累加。。。。。 6 */ 7 #include8 #include 9 #include 10 #include 11 #include 12 13 using namespace std;14 #define lson l,m,rt<<115 #define rson m + 1, r, rt<<1|116 const int maxn = 1e5 + 5;17 int s[maxn];18 int n, d;19 int san[maxn], tot;20 int sum[maxn << 2];21 void pushUp(int rt){22 sum[rt] = max(sum[rt<<1], sum[rt<<1|1]);23 }24 void update(int pos, int c, int l, int r, int rt){25 if (l == r){26 sum[rt] = c;//注意27 return ;28 }29 int m = (l + r) >> 1;30 if (pos <= m) update(pos, c, lson);31 else update(pos, c, rson);32 pushUp(rt);33 }34 int query(int L, int R, int l, int r, int rt){35 if (L <= l && R >= r){36 return sum[rt];37 }38 int m = (l + r) >> 1;39 int ret = 0;40 if (L <= m) ret = query(L, R, lson);41 if (R > m) ret = max(ret, query(L, R, rson));42 return ret;43 }44 int main(){45 while (~scanf("%d%d", &n, &d)){46 tot = 0;47 for (int i = 1; i <= n; ++i){48 scanf("%d", &s[i]);49 san[tot++] = s[i];50 }51 sort(san, san + tot);52 tot = unique(san, san + tot) - san;53 54 memset(sum, 0, sizeof(sum));55 int ans = 0;56 for (int i = 1; i <= n; ++i){57 int pos = lower_bound(san, san + tot, s[i]) - san + 1;58 int l = lower_bound(san, san + tot, s[i] - d) - san + 1;59 int r = upper_bound(san, san + tot, s[i] + d) - san;60 int que = query(l, r, 1, tot, 1) + 1;61 //cout << " l = " << l << " r = " << r << endl;62 ans = max(ans, que);63 //cout << " ans = " << ans << endl;64 update(pos, que, 1, tot, 1);65 }66 printf("%d\n", ans);67 }68 return 0;69 }