题解：P13968 [VKOSHP 2024] Classics

· · 题解

双倍经验：P4309 [TJOI2013] 最长上升子序列。话说凭啥这题是蓝，那题是紫。

分析

我们需要在每次插入时获得 LIS。

我们可以直接模拟得到所有插入操作之后的序列。

然后枚举每一个数。由于是按顺序插入，所以先处理小的，再处理大的，就不会影响答案。

用 pos_i 表示 i 在最终数组中的位置，维护 \max\limits_{i=1}^{pos_i-1}dp_i，即 dp 数组中 [1,pos_i) 的最大值即可。最后更新一下 dp_{pos_i} 就行了。

:::info[那我万一有一个 j 满足 j>i,pos_j<pos_i 怎么办] 这时候 j 还没有插入，没有影响。 :::

你可以使用 rope 或者支持分裂的平衡树维护。注意 rope 的下标是 0 开始的。

注意！线段树无法处理 [1,1) 这种无效区间，所以记得特判 pos_i=1。

AC record。

#include<bits/extc++.h>
#define endl '\n'
using namespace std;
using namespace __gnu_cxx;
rope<int> r;
const int maxn=2e5+5;
struct T{
    struct node{
        int l,r,max;
    }t[maxn*4];
#define ls id<<1
#define rs id<<1|1
    void up(int id){t[id].max=max(t[ls].max,t[rs].max);}
    void build(int id,int l,int r){
        t[id].l=l,t[id].r=r;
        if(l==r){
            t[id].max=0;
            return;
        }
        int mid=(l+r)>>1;
        build(ls,l,mid);
        build(rs,mid+1,r);
        up(id);
    }
    int query(int id,int l,int r){
        if(t[id].l>r||t[id].r<l)return INT_MIN;
        if(l<=t[id].l&&t[id].r<=r)return t[id].max;
        return max(query(ls,l,r),query(rs,l,r));
    }
    void update(int id,int x,int val){
        if(t[id].l>x||t[id].r<x)return;
        if(t[id].l==t[id].r&&t[id].l==x){t[id].max=val;return;}
        update(ls,x,val);update(rs,x,val);
        up(id);
    }
}t;
int ans[maxn],pos[maxn];
int main(){
    int n;
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){int x;cin>>x;r.insert(x-1,i);}
    for(int i=0;i<n;i++)pos[r[i]]=i+1;
    t.build(1,1,n);
    for(int i=1;i<=n;i++){//枚举K
        if(pos[i]==1)ans[i]=1;//特判！
        else ans[i]=t.query(1,1,pos[i]-1)+1;//[1,pos_i)
        t.update(1,pos[i],ans[i]);
    }
    for(int i=1;i<=n;i++){
        ans[i]=max(ans[i],ans[i-1]);
        cout<<ans[i]<<endl;
    }
    return 0;
}