ABC339E 题解

KSCD_ · 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;
}