3173: [Tjoi2013]最长上升子序列

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 2253  Solved: 1136

[ ][ ][ ]

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

 

用平衡树构造序列后,对整个序列求一个lis 

设f[i]表示i结尾的lis 可以确定这样的lis一定是插入i后的答案(因为之前的都比i小)

输出答案的时候取前缀max

#include
     
      #include
      
       #include
       
        #include
        
         #define ll long long#define N 100050using namespace std;int n,rt,cnt,num,a[N],b[N],ans[N],ls[N],siz[N],rd[N],rs[N];void update(int u){siz[u]=siz[ls[u]]+siz[rs[u]]+1;}void lturn(int &u){    int t=rs[u];rs[u]=ls[t];ls[t]=u;    update(u);update(t);u=t;}void rturn(int &u){    int t=ls[u];ls[u]=rs[t];rs[t]=u;    update(u);update(t);u=t;}void insert(int &u,int k){    if(!u){        u=++cnt;siz[u]=1;        rd[u]=rand();        return;    }    siz[u]++;    if(siz[ls[u]]
         
          tot){            b[++tot]=a[i];            ans[a[i]]=tot;        }        else{            ans[a[i]]=p;            b[p]=a[i];        }    }}int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++){        int p;        scanf("%d",&p);        insert(rt,p);    }    dfs(rt);solve();    //for(int i=1;i<=n;i++)printf("%d ",a[i]);    for(int i=1;i<=n;i++){        ans[i]=max(ans[i],ans[i-1]);        printf("%d\n",ans[i]);    }    return 0;}