Eva

Time Limit: 10 Sec  Memory Limit: 128 MB
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

/**************************************************************

    Problem: 3173

    User: ictsing

    Language: C++

    Result: Accepted

    Time:848 ms

    Memory:4808 kb

****************************************************************/

 

//BZOJ3173 [Tjoi2013]最长上升子序列

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <algorithm>

#include <cstring>

using namespace std;

int root=0,tot=0;

const int mt = 100000+5;

const int inf = 1000000000;

int ls[mt],rs[mt],rnd[mt],sz[mt],w[mt];

int dp[mt];

int cnt=0;

int val[mt];

inline int read()

{

    int num=0,flag=1;

    char ch;

    do{

       ch=getchar();

       if(ch=='-') flag=-1;

    }while(ch<'0'||ch>'9');

    do{

       num=num*10+ch-'0';

       ch=getchar();

    }while(ch>='0'&&ch<='9');

    return num*flag;

}

void update(int rt)

{

    sz[rt]=sz[ls[rt]]+sz[rs[rt]]+w[rt];

}

void lturn(int &k)

{

    int t=rs[k];

    rs[k]=ls[t];

    ls[t]=k;

    update(k);

    update(t);    

    k=t;

}

void rturn(int &k)

{

    int t=ls[k];

    ls[k]=rs[t];

    rs[t]=k;

    update(k);

    update(t);

    k=t;

}   

void insrt(int &rt,int x)

{

    if(!rt)

    {

        rt=++tot;

        sz[rt]=w[rt]=1;

        rnd[rt]=rand();

        ls[rt]=rs[rt]=0;

        return ;

    }

    sz[rt]++;

    if(sz[ls[rt]]>=x)

    {

        insrt(ls[rt],x);

        if(rnd[ls[rt]]<rnd[rt]) rturn(rt);

    }

    else

    {

        insrt(rs[rt],x-sz[ls[rt]]-w[rt]);

        if(rnd[rs[rt]]<rnd[rt]) lturn(rt);

    }

}

int qwq=0;

void dfs(int rt)

{

    if(!rt) return ;

    if(ls[rt])  dfs(ls[rt]);

    val[++qwq]=rt;

    if(rs[rt]) dfs(rs[rt]);

}

int ans[mt];

int mn[mt],mx;

int main()

{

    int n=read();

    for(int i=1;i<=n;i++)

    {

        int x=read();

        insrt(root,x);

    }

    dfs(root);

    /*memset(dp,127,sizeof(dp));

    dp[0]=-inf;int mx=0;*/

    /*for(int i=1;i<=n;i++)

        cout<<val[i]<<endl;*/

    /*for(int i=1;i<=n;i++)

    {

        int t=upper_bound(dp,dp+mx+1,val[i])-dp;

        if(dp[t-1]<=val[i])

        {

            dp[t]=min(dp[t],val[i]);

            ans[val[i]]=t;

            mx=max(mx,t);

        }

    }*/

    memset(mn,127,sizeof(mn));

    mn[0]=-inf;

    for(int i=1;i<=n;i++)

    {

        int t=upper_bound(mn,mn+mx+1,val[i])-mn;

        if(mn[t-1]<=val[i])

        {

            mn[t]=min(mn[t],val[i]);

            ans[val[i]]=t;

            mx=max(t,mx);

        }

    }    

    for(int i=1;i<=n;i++)

    {

        ans[i]=max(ans[i],ans[i-1]);

        printf("%d\n",ans[i]);

    }

    return 0;

}