题解：P13968 [VKOSHP 2024] Classics

· · 题解

我们不妨先维护出按照题目要求插入数据后的数列 a，很明显，每次将 i 插入 第 p 位就是要找到数列 a 中的第 p-1 号元素，然后将 i 插入到 p-1 号元素与 p 号元素之间，这可以非常轻松的用平衡树维护，具体来说就是将排名小于等于 p-1 与大于 p 的两棵子树分裂，然后新建节点记录 i,最后将这三棵子树合并。

接下来，我们分析 i 插入到数列 a 的第 j 位，由于 1 到 n 是从小到大插入的，所以我们不难发现 a_j 是不可能对 a_k,k\in[j+1,n] 中已经插入的元素造成贡献的，而对 a_k,k\in[1,j-1] 而言我们只需找出其中以 a_k,k\in[1,j-1] 结尾的最大的最长上升子序列长度 l，那么以 a_j 为结尾的最长上升子序列长度为 l+1，特别的，当 a_j 前面没有元素时，长度即为 1，这一过程明显可以用线段树实现。

CODE

#include<bits/stdc++.h>
using namespace std;
int n,rt,a[200005],idx,b[200005],tt[800005];
struct node{
    int l,r,sz,val,pri;
}tr[200005];
void split(int p,int x,int &l,int &r){
    if(!p){
        l=0;
        r=0;
        return;
    }
    if(tr[tr[p].l].sz+1>x){
        r=p;
        split(tr[p].l,x,l,tr[p].l);
        tr[p].sz=tr[tr[p].l].sz+tr[tr[p].r].sz+1;
    }
    else{
        l=p;
        split(tr[p].r,x-tr[tr[p].l].sz-1,tr[p].r,r);
        tr[p].sz=tr[tr[p].l].sz+tr[tr[p].r].sz+1;
    }
}
void check(int x){
    if(!x)
        return;
    check(tr[x].l);
    a[++idx]=tr[x].val;
    check(tr[x].r);
}
int merge(int u,int v){
    if(!u||!v)
        return u|v;
    if(tr[u].pri>tr[v].pri){
        tr[u].r=merge(tr[u].r,v);
        tr[u].sz=tr[tr[u].l].sz+tr[tr[u].r].sz+1;
        return u;
    }
    tr[v].l=merge(u,tr[v].l);
    tr[v].sz=tr[tr[v].l].sz+tr[tr[v].r].sz+1;
    return v;
}
int query(int p,int s,int t,int r){
    if(r==0)
        return 0;
    if(t<=r)
        return tt[p];
    int mid=(s+t)>>1,res=query(p<<1,s,mid,r);
    if(r>mid)
        res=max(res,query(p<<1|1,mid+1,t,r));
    return res;
}
void modify(int p,int l,int r,int x,int y){
    if(l==r){
        tt[p]=y;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid)
        modify(p<<1,l,mid,x,y);
    else
        modify(p<<1|1,mid+1,r,x,y);
    tt[p]=max(tt[p<<1],tt[p<<1|1]);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    srand(time(NULL));
    cin>>n;
    int x;
    cin>>x;
    rt=1;
    tr[1].val=1;
    tr[1].sz=1;
    tr[1].pri=rand();
    for(int i=2;i<=n;i++){
        cin>>x;
        int l,r;
        split(rt,x-1,l,r);
        tr[i].pri=rand();
        tr[i].val=i;
        tr[i].sz=1;
        rt=merge(l,merge(i,r));
    }
    check(rt);
    for(int i=1;i<=n;i++)
        b[a[i]]=i;
    int maxn=0;
    for(int i=1;i<=n;i++){
        int ttt=query(1,1,n,b[i]-1);
        modify(1,1,n,b[i],ttt+1);
        cout<<(maxn=max(maxn,ttt+1))<<endl;
    }
    return 0;
}