P8776 最长不下降子序列 题解

· · 题解

原题链接

不错的题，这里提供一个树状数组写法。

首先对于序列每一个位置，求出 L_i,R_i 分别表示以 i 位置为结尾，为开始的最长不下降子序列，求法就是正着做一遍朴素的最长不下降子序列，反着做一遍最长不上升子序列，注意用 n \log n 做法。

接着考虑拼接。

首先我们可以得出一个结论：改变 k 个数一定比改变更少的数优秀。这很显然，因为我们可以把改成和原来相同也看作改变。

那接下来就好做了，我们对每一个位置 i ，贪心地考虑它前面 k 个数被改成与它相同，那只需要找一个 j 属于 [1,i-k-1] ，使得 val_j \leq val_i 且 L_j 最大，然后用 L_j + k + R_i 更新答案就行了。

温馨提示：因为要用三个树状数组，最好把树状数组写成类更方便。

update on 11.19: 之前有一点没有说清楚，其实这个做法隐含了一个贪心，那就是如果改变 [L,R] 这 k 个数，我们只考虑其去配合以 R+1 为左端点的最长不降序列，因为就算它配合以更后面的数 x 为左端点的最长不降序列有更优答案，那它也不会比枚举改变 [x-k,x-1] 这 k 个数时去配合 x 更优，因为那时 L_j 选择更广。所以改变 [L,R] 这 k 个数时，自然是改变成 val_{R+1} 更优。

update on 11.25: 代码有一点小锅，已修。

update on 2025.5.12: 代码又有一点小锅，已修。

下附代码：

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;
int n,k,ans,val[N],L[N],R[N];
vector<int> vec;
struct BIT
{
    int C[N];
    inline void add(int x,int y){for(;x<=n+1;x+=x&-x)   C[x]=max(C[x],y);}
    inline int query(int x)
    {
        int ans=0;
        for(;x;x-=x&-x) ans=max(ans,C[x]);
        return ans;
    }
}le,re,s;
int main()
{
    scanf("%d%d",&n,&k);
    val[0]=1;val[n+1]=n+1;
    for(int i=1;i<=n;i++)   scanf("%d",&val[i]);
    for(int i=1;i<=n;i++)   vec.push_back(val[i]);
    sort(vec.begin(),vec.end());
    vec.erase(unique(vec.begin(),vec.end()),vec.end());
    for(int i=1;i<=n;i++)   val[i]=lower_bound(vec.begin(),vec.end(),val[i])-vec.begin()+1;
    for(int i=1;i<=n;i++)
    {
        L[i]=le.query(val[i])+1;
        le.add(val[i],L[i]);
    }
    for(int i=n;i>=1;i--)
    {
        R[i]=re.query(n-val[i]+1)+1;
        re.add(n-val[i]+1,R[i]);
    }
    for(int i=k+1;i<=n+1;i++)
    {
        s.add(val[i-k-1],L[i-k-1]);
        ans=max(ans,s.query(val[i])+k+R[i]);
    }   
    printf("%d",ans);
    return 0;   
}

完结撒花~