AT_abl_d Flat Subsequence 题解

分析

线段树模板题。

一眼 DP。定义状态函数 \(\mathit{f}_i\) 表示前 \(i\) 个数中，必选 \(\mathit{A}_i\) 时 \(B\) 的最大长度。则有转移方程：\(\mathit{f}_i=\max\{f_j |((1\le j \le i-1 )\land (-k \le A_i-A_j \le k))\}+1\)。答案就是 \(\max\limits_{i=1}^{n} \mathit{f}_i\)。

很显然暴力枚举 \(j\) 的复杂度是 \(O(n^2)\) 的，考虑优化。使用线段树维护区间 \([A_i-k,A_i+k]\) 的最大 \(f\) 的值。在转移 \(\mathit{f}_i\) 的时候一定能保证找出来的这个最大值是在 \(\mathit{f}_1\) 到 \(\mathit{f}_{i-1}\) 中出现过的（\(0\) 除外）。这个的复杂度是 \(O(n\log n)\)，能过。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register
#define il inline
#define PII pair<int,int>
#define x first
#define y second

const int N=3e5+10,inf=3e5;
int n,k,a[N];
int f[N],ans;
struct node{
	int l,r,mx;
}tr[(inf|1)<<2];

il void up(int now){tr[now].mx=max(tr[now<<1].mx,tr[now<<1|1].mx);}
il void build(int now,int l,int r){
	tr[now].l=l,tr[now].r=r;
	if(l==r) return ;
	int mid=l+r>>1;
	build(now<<1,l,mid),build(now<<1|1,mid+1,r);
}
il void insert(int now,int x,int k){
	if(tr[now].l==tr[now].r) tr[now].mx=max(tr[now].mx,k);
	else{
		int mid=tr[now].l+tr[now].r>>1;
		if(x<=mid) insert(now<<1,x,k);
		else insert(now<<1|1,x,k);
		up(now);
	}
}
il int query(int now,int l,int r){
	if(tr[now].l>=l&&tr[now].r<=r) return tr[now].mx;
	int maxx=0,mid=tr[now].l+tr[now].r>>1;
	if(l<=mid) maxx=max(maxx,query(now<<1,l,r));
	if(mid<r) maxx=max(maxx,query(now<<1|1,l,r));
	return maxx;
}

il void solve(){
	cin>>n>>k;
	for(re int i=1;i<=n;++i) cin>>a[i];
	build(1,0,inf);
	for(re int i=1;i<=n;++i){
		f[i]=query(1,max(0LL,a[i]-k),min(inf,a[i]+k))+1;
		insert(1,a[i],f[i]),ans=max(ans,f[i]);
	}
	cout<<ans;
}

signed main(){
	solve();
	return 0;
}