AtCoder Beginner Contest 339 E - Smooth Subsequence 题解

题意

给定一个长度为 $N$ 的序列 $A$ 和整数 $D$ ，求出序列 $A$ 中满足任意两个相邻元素之差的绝对值都不小于 $D$ 的子串的最大长度。

数据范围

$1\leq N \leq 5\times10^5$
$0\leq D \leq 5\times10^5$
$1\leq A_i \leq 5\times10^5$
所有输入数据都是整数。

思路

显然是一道 dp 题。

状态设计&转移

用 $f_i$ 代表以 $a_i$ 为结尾的 $A$ 的满足要求的子串中的最大长度，则我们只要找一个符合要求的 $j$ 并把以 $a_j$ 为结尾的最长子串接在 $a_i$ 之前即可，于是可以得到以下状态转移方程：

$f_i=\max\{f_j\}+1 \ (j<i,|a_i-a_j|\leq D)$

但从 $1$ 到 $i$ 枚举选出最大的 $j$ 时间复杂度为 $\mathcal{O}(N^2)$ ，无法通过本题，所以考虑用数据结构优化，而线段树可以做到用 $\log N$ 的时间复杂度查询和修改区间最值，于是我们可以建立一棵以序列 $A$ 中的值为下标的线段树来维护 $f$ ，每次求解 $f_i$ 时查询在区间 $[\max(1,a_i-d),\min(5\times 10^5,a_i+d)]$ 内的最大值即可。

答案即为 $\max\{f_i\}(1\leq i\leq N)$ 。

代码

const int N = 5e5+5;
int a[N];
int tree[N*4];    //区间查询，单点修改的线段树
inline void pushup(int p){tree[p] = max(tree[p<<1],tree[(p<<1)+1]);}
void update(int d,int l,int r,int p,int val){
    if(d==l && l==r)	tree[p] = val;
    else{
        int mid = (l+r)>>1;
        if(mid>=d)	update(d,l,mid,p<<1,val);
        else update(d,mid+1,r,(p<<1)+1,val);
        pushup(p);
    }
}
int query(int l,int r,int nl,int nr,int p){
    if(nl>=l && nr<=r)	return tree[p];
    else{
        int mid = (nl+nr)>>1;
        int now = 0;
        if(mid>=l)	now = max(now,query(l,r,nl,mid,p<<1));
        if(mid+1<=r)	now = max(now,query(l,r,mid+1,nr,(p<<1)+1));
        return now;
    }
}
int ans[N];
void solve(){
    int n;cin>>n;
    int d;cin>>d;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int maxans = 0;
    for(int i=1;i<=n;i++){
        int l = max(1,a[i]-d),r = min(N,a[i]+d);
        int now = query(l,r,0,N,1);
        ans[i] = now+1;
        update(a[i],0,N,1,ans[i]);
        maxans = max(ans[i],maxans);
    }
    cout<<maxans;
}