题目描述

Description

给定一个序列，初始为空。现在我们将1到N的数字插入到序列中，每次将一个数字插入到一个特定的位置。每插入一个数字，我们都想知道此时最长上升子序列长度是多少？

Input

第一行一个整数N，表示我们要将1到N插入序列中，接下是N个数字，第k个数字Xk，表示我们将k插入到位置Xk（0<=Xk<=k-1,1<=k<=N）

Output

N行，第i行表示i插入Xi位置后序列的最长上升子序列的长度是多少。

Sample Input

3
0 0 2

Sample Output

1
1
2

HINT

100%的数据 n<=100000

题目分析

注意到一个非常好的性质 每次插入的数字是单调上升的
那么也就是说 每次插入的值 都大于它前面所有的数字 所以 每次插入的数的dp值是之前所有数的最大dp值+1
用非旋treap维护序列 维护前缀dp最大值即可

#include <cstdio>
#include <cstring>
#include <cmath>
#include <ctime>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int,int> par;
int n,m;
int val[101000*3],size[101000*3],key[101000*3],lson[101000*3],rson[101000*3];
int dp[101000*3],maxx[101000*3];
int tot,root;
void update(int x)
{
    maxx[x]=dp[x];
    size[x]=size[lson[x]]+size[rson[x]]+1;
    maxx[x]=max(max(maxx[lson[x]],maxx[rson[x]]),maxx[x]);
}
int merge(int x,int y)
{
    if(x==0||y==0) return x|y;
    if(key[x]<key[y])
    {
        lson[y]=merge(x,lson[y]),update(y);
        return y;
    }
    rson[x]=merge(rson[x],y),update(x);
    return x;
}
par split(int x,int k)
{
    if(k==0) return make_pair(0,x);
    int l=lson[x],r=rson[x];
    if(k==size[lson[x]])
    {
        lson[x]=0,update(x);
        return make_pair(l,x);
    }
    if(k==size[lson[x]]+1)
    {
        rson[x]=0,update(x);
        return make_pair(x,r);
    }
    par t;
    if(k<size[lson[x]])
    {
        t=split(l,k);
        lson[x]=t.second,update(x);
        return make_pair(t.first,x);
    }
    else
    {
        t=split(r,k-size[lson[x]]-1);
        rson[x]=t.first,update(x);
        return make_pair(x,t.second);
    }
}
void output(int x)
{
    if(lson[x]) output(lson[x]);
    printf("%d:%d:%d:%d\n",val[x],maxx[x],lson[x],rson[x]);
    if(rson[x]) output(rson[x]);
}
int main()
{
    scanf("%d",&n);
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        int x,y;
        scanf("%d",&x);
        size[++tot]=1,val[tot]=i,key[tot]=rand()*rand();
        par t1;
        t1=split(root,x);
        dp[tot]=maxx[tot]=maxx[t1.first]+1;
        ans=max(ans,dp[tot]);
        printf("%d\n",ans);
        root=merge(merge(t1.first,tot),t1.second);
    }
    return 0;
}