题解：P13968 [VKOSHP 2024] Classics

· · 题解

题目大意：

有一个 1 到 n 的排列，第 i 次操作讲 i 添加到当前数组中的第 p_i 个位置上，求每次操作完后数组中的最长上升子序列。

思路分析：

首先我们考虑找到每个数最后的位置。显然从前往后依次加数是比较麻烦的，我们考虑倒着做，每次就相当于把这个数添加到剩下数组里的第 p_i 个位置上，然后删掉这个位置。相当于是查找第 k 小以及删除，很明显这个可以用平衡树做。

然后我们再考虑怎么求出答案。我们设 dp_i 表示以 i 结尾的最长上升子序列，由于每次插入的数是递增的，所以 dp_i=\max_{j=1}^{i-1} dp_j+1，直接用线段树求区间最值就行了。

完整代码：

#include <bits/stdc++.h>
#define l(a) d[a].lson
#define r(a) d[a].rson
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pb push_back
using namespace std;
int Time=clock();
bool mst;
const int N=200005;
struct node{
    int v,cnt,siz,lson,rson,rnd;
};
int n,cnt,p[N],rt,ans,pos[N];
uniform_int_distribution<int> u;
mt19937 mt(chrono::system_clock().now().time_since_epoch().count());
namespace treap{
    node d[N];
    inline void zag(int &a){
        int t=r(a);
        r(a)=l(t),l(t)=a,d[t].siz=d[a].siz,d[a].siz=d[l(a)].siz+d[r(a)].siz+d[a].cnt,a=t;
    }
    inline void zig(int &a){
        int t=l(a);
        l(a)=r(t),r(t)=a,d[t].siz=d[a].siz,d[a].siz=d[l(a)].siz+d[r(a)].siz+d[a].cnt,a=t;
    }
    inline void insert(int &a,int v){
        if(a==0){
            a=++cnt,d[a].siz=d[a].cnt=1,d[a].v=v,d[a].rnd=u(mt);
            return ;
        }
        d[a].siz++;
        if(v==d[a].v)  d[a].cnt++;
        else if(v<d[a].v){
            insert(l(a),v);
            if(d[l(a)].rnd<d[a].rnd)  zig(a);
        }
        else{
            insert(r(a),v);
            if(d[r(a)].rnd<d[a].rnd)  zag(a);
        }
    }
    inline void remove(int &a,int v){
        if(v==d[a].v){
            if(d[a].cnt>1)  d[a].cnt--,d[a].siz--;
            else if(l(a)==0||r(a)==0)  a=l(a)+r(a);
            else{
                if(d[l(a)].rnd<d[r(a)].rnd)  zig(a);
                else  zag(a);
                remove(a,v);
            }
            return ;
        }
        d[a].siz--;
        if(v<d[a].v)  remove(l(a),v);
        else  remove(r(a),v);
    }
    inline int query(int a,int x){
        while(1){
            if(x<=d[l(a)].siz)  a=l(a);
            else if(x<=d[l(a)].siz+d[a].cnt)  return d[a].v;
            else  x-=d[l(a)].siz+d[a].cnt,a=r(a);
        }
    }
}
namespace segtree{
    int tr[4*N];
    void update(int l,int r,int x,int y,int rt){
        if(l==r){
            tr[rt]=y;
            return ;
        }
        int mid=l+r>>1;
        if(x<=mid)  update(l,mid,x,y,rt<<1);
        else  update(mid+1,r,x,y,rt<<1|1);
        tr[rt]=max(tr[rt<<1],tr[rt<<1|1]);
    }
    int query(int l,int r,int L,int R,int rt){
        if(L>R)  return 0;
        if(L<=l&&R>=r)  return tr[rt];
        int ans=0,mid=l+r>>1;
        if(L<=mid)  ans=max(ans,query(l,mid,L,R,rt<<1));
        if(R>mid)  ans=max(ans,query(mid+1,r,L,R,rt<<1|1));
        return ans;
    }
}
bool med;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>p[i];
    for(int i=1;i<=n;i++)
        treap::insert(rt,i);
    for(int i=n;i>=1;i--){
        pos[i]=treap::query(rt,p[i]);
        treap::remove(rt,pos[i]);
    }
    for(int i=1;i<=n;i++){
        int t=segtree::query(1,n,1,pos[i]-1,1)+1;
        segtree::update(1,n,pos[i],t,1);
        ans=max(ans,t);
        cout<<ans<<'\n';
    }
    #ifndef ONLINE_JUDGE
    cerr<<"Time:"<<fixed<<setprecision(5)<<1.0*(clock()-Time)/CLOCKS_PER_SEC<<"s"<<endl;
    cerr<<"Memory:"<<fixed<<setprecision(5)<<1.0*(&med-&mst)/1024/1024<<"MB";
    #endif
    return 0;
}