[HUST][1022][K-diff subsequence][线段树＋DP]

题意在一个整数序列中求出相邻元素相差不超过 m 的最长子序列。

易得到 dp 方程。 dp[i]= max{ dp[j]+ 1,  1<= j < i 且 d[i] 与 d[j] 相差不超过 m }  方程复杂度为  o(n^2) 。

用线段树对方程进行优化，先将数据离散化，使得数据范围变成 [1,n]。在上述方程求 dp[i] 的值时，对 i 前面的数遍历找出最优值相当于在区间 [ d[i]- m, d[i]+ m ] 内找出最优值，这个可以用线段树优化，使得复杂度达到 nlogn。

代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

int const N= 102410;
int tb[N<<2];
int n, k, dat[N], sn[N];

int query( int x, int y, int L, int R, int rt ){
	if( L== x && y== R ) return tb[rt];
	int mid= (L+ R)>>1;
	if( y<= mid ) return query( x, y, L, mid, rt<<1 );
	else if( x> mid ) return query( x, y, mid+ 1, R, rt<<1|1 );
	else{
		int a= query( x, mid, L, mid, rt<<1 );
		int b= query( mid+ 1, y, mid+ 1, R, rt<<1|1 );
		return max(a,b);
	}
}

void update( int x, int y, int L, int R, int rt ){
	if( L== R ){
		tb[rt]= max( tb[rt], y ); return; }
	int mid= (L+ R)>> 1;
	if( x<= mid ) update( x, y, L, mid, rt<<1 );
	else update( x, y, mid+ 1, R, rt<<1|1 );
	tb[rt]= max( tb[rt<<1], tb[rt<<1|1] );
}

int main(){
	int test;
	scanf("%d",&test );
	while( test-- ){
		scanf("%d%d",&n,&k );
		for( int i= 1; i<= n; ++i ) scanf("%d", dat+ i );
		copy( dat+ 1, dat+ 1+ n, sn+ 1 );
		sort( sn+ 1, sn+ 1+ n );
		fill( tb, tb+ (n<<2), 0 );
		
		int ans= 0;
		for( int i= 1; i<= n; ++i ){
			int x= lower_bound( sn+ 1, sn+ 1+ n, dat[i]- k )- sn;
			int y= upper_bound( sn+ 1, sn+ 1+ n, dat[i]+ k )- sn- 1;
			
			int tmp= query( x, y, 1, n, 1 );
			if( tmp+ 1> ans ) ans= tmp+ 1;
			
			x= lower_bound( sn+ 1, sn+ 1+ n, dat[i] )- sn;
			update( x, tmp+ 1, 1, n, 1 );
		}
		printf("%d\n", ans );
	}
	
	return 0;
}