本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-03 23:14:39

题意

给定一个序列 $A$ ，求相邻两项绝对差不大于 $D$ 的最长子序列长度。

分析

子序列问题很容易想到动态规划。

设 $f_i$ 为以 $A_i$ 为结尾的合法子序列长度最大值。

易得 $f_i=max(f_j)+1 $ ,其中 $j<i$ 且 $\left|A_i-A_j\right|\le D$。

暴力枚举时间复杂度为 $O(n^2)$，必炸。

考虑优化到 $O(n\log n)$ 以通过本题。

我们发现对于一个 $A_i$，可以取到的 $A_j$ 范围为 $A_i-D \le A_j \le A_i+D$。

现在要求在 $O(\log n)$ 的时间复杂度下查找到这个区间内 $f_j$ 的最大值。

由于 $A_i$ 域值为 $5\times10^5$，可以使用线段树优化。

设 $s_i$ 为目前以 $i$ 为结尾的合法子序列长度最大值。

初始 $s$ 数组均为 $0$，建出线段树。

枚举到每个 $A_i$ 时，所有符合 $j<i$ 的 $A_j$ 已经全部更新完。

因此查找该区间最大值并加一，以此来更新答案和 $A_i$ 对应 $s$ 的值。

此时若更新了 $s$ 的值，就同时在线段树内维护。

最后输出答案即可。

代码

#include<iostream>
#include<cmath>
using namespace std;
const int N=5e5+10;
const int M=5e5;\/\/N为开数组用的范围，M为实际范围 
int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){ if(ch=='-') w=-1;  ch=getchar();}
	while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar();}
	return s*w;
}
int n,d,ans=0,t=1;
int s[N],A[N];\/\/A为原数组，s为目前线段树中存储的最大值 
struct nod
{
	int u,l,r,s;
}a[N*2];\/\/线段树记得开两倍范围
void pushup(int u)
{
	a[u].s=max(a[a[u].l].s,a[a[u].r].s);
}\/\/传递孩子的最大值给父亲 
void build(int u,int l,int r)
{
	if(l==r)
	{
		a[u].s=s[l];
		return;
	} 
	int mid=(l+r)\/2;
	a[u].l=++t;
	build(t,l,mid);
	a[u].r=++t;
	build(t,mid+1,r);
	pushup(u);
}\/\/建树
void change(int u,int l,int r,int ll,int k)
{
	if(l==r&&l==ll)
	{
		a[u].s=k;
		return;
	}
	int mid=(l+r)\/2;
	if(ll<=mid)
		change(a[u].l,l,mid,ll,k);
	else
		change(a[u].r,mid+1,r,ll,k);
	pushup(u);
}\/\/更改元素并维护最大值 
int check(int u,int l,int r,int ll,int rr)
{
	if(l>=ll&&r<=rr)
		return a[u].s;
	int mid=(l+r)\/2,ans=0;
	if(ll<=mid)
		ans=max(ans,check(a[u].l,l,mid,ll,rr));
	if(rr>mid)
		ans=max(ans,check(a[u].r,mid+1,r,ll,rr));
	return ans;
}\/\/查询区间最大值
int main()
{
	n=read(),d=read();
	for(int i=1;i<=n;i++)
		A[i]=read();
	build(1,1,M);\/\/建树
	for(int i=1;i<=n;i++)
	{
		int l=max(1,A[i]-d);
		int r=min(M,A[i]+d);\/\/注意范围要在1-5e5之间，避免越界 
		int maxx=check(1,1,M,l,r);\/\/查询最大值 
		if(ans<maxx+1)
			ans=maxx+1;\/\/更新答案 
		if(s[A[i]]<maxx+1)
		{
			s[A[i]]=maxx+1;
			change(1,1,M,A[i],maxx+1);
		}\/\/更新以Ai为结尾的最大长度并维护线段树
	}
	cout<<ans;
	return 0;
}