题解：P15070 [UOI 2024 II Stage] Sequence

· · 题解

题目链接：P15070 [UOI 2024 II Stage] Sequence

Part 1 动态规划设计

定义 f_{i,j} 为 b 从前 i 个元素里选择，且最后一个元素为 j 时的答案，容易得到转移：

f_{i,j}=\max\limits_{l-j \leqslant k \leqslant r-j}^{1 \leqslant x < i}f_{x,k}+1

若没有符合条件的 k，则为 0。

Part 2 线段树优化

当遍历到 i 时，定义 s_{l,r} 为 \max\limits_{l \leqslant k \leqslant r}^{1 \leqslant x < i}f_{x,k}，则 f_{i,j} 可以直接求出来，然后再给 s_{l,r} 更新。

也就是说，我们要支持单点修改和查询区间最大值。自然而然想到线段树。

Part 3 算法实现

由于末元素只可能是序列里出现过的元素，因此线段树也不需要开 10^{17}，所以我们先离散化。

然后我们二分出可以给 a_i 转移的区间，找到不小于 l-a_i 的最大元素和不大于 r-a_i 的最小元素，用线段树转移即可。

Part 4 参考代码

#include<bits/stdc++.h>
using namespace std;
const int N=500001;
int n,b[N],tot;
int s[N<<2],L[N<<2],R[N<<2];
long long l,r,a[N],c[N];
void build(int u,int l,int r){
    L[u]=l,R[u]=r;
    if(l<r){
        int mid=(l+r)/2;
        build(u*2,l,mid);
        build(u*2+1,mid+1,r);
    }
}
int update(int u,int x,int k){
    if(L[u]<=x&&x<=R[u]){
        if(L[u]==R[u])return s[u]=max(s[u],k);
        return s[u]=max(update(u*2,x,k),update(u*2+1,x,k));
    }
    return s[u];
}
int query(int u,int l,int r){
    if(l>r||l>R[u]||L[u]>r)return 0;
    if(l<=L[u]&&R[u]<=r)return s[u];
    return max(query(u*2,l,r),query(u*2+1,l,r));
}
int find(long long x){
    int l=1,r=tot,mid,ans=0;
    while(l<=r){
        mid=(l+r)/2;
        if(c[mid]<=x)ans=mid,l=mid+1;
        else r=mid-1;
    }
    return ans;
}
int main(){
    cin>>n>>l>>r;
    for(int i=1;i<=n;i++)cin>>a[i],c[i]=a[i];
    sort(c+1,c+1+n);
    tot=unique(c+1,c+1+n)-(c+1);
    build(1,1,tot);
    for(int i=1;i<=n;i++)update(1,lower_bound(c+1,c+1+tot,a[i])-c,query(1,lower_bound(c+1,c+1+tot,l-a[i])-c,find(r-a[i]))+1);
    cout<<s[1];
    return 0;
}