bzoj3173 [Tjoi2013]最长上升子序列

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

Source

分析了一下觉得随便splay都行但是懒得splay了就

提前预处理出每个点最终的位置 然后直接用树状数组维护最大值即可 因为1~n插入只会对后面的产生影响且+1

#include<cstdio>
#include<cctype>
#include<algorithm>
#define lc (x<<1)
#define rc (x<<1|1)
using namespace std;
inline char gc(){
    static char now[1<<16],*S,*T;
    if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
    return *S++;
}
inline int read(){
    int x=0,f=1;char ch=gc();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=gc();}
    while(isdigit(ch)) x=x*10+ch-'0',ch=gc();
    return x*f;
}
const int N=100010;
int v[N<<2];
inline void build(int x,int l,int r){
    if (l==r) {v[x]=1;return;}int mid=l+r>>1;
    build(lc,l,mid);build(rc,mid+1,r);v[x]=v[lc]+v[rc];
}
inline int query(int x,int l,int r,int p){
    if (l==r) {v[x]=0;return l;}int mid=l+r>>1,tmp;
    if (p<=v[lc]) tmp=query(lc,l,mid,p);
    else tmp=query(rc,mid+1,r,p-v[lc]);v[x]=v[lc]+v[rc];return tmp;
}
int x[N],rk[N],s[N],n;
inline void add(int x,int v){
    while(x<=n) s[x]=max(s[x],v),x+=x&-x;
}
inline int qr(int x){static int tmp;
    tmp=0;while(x) tmp=max(tmp,s[x]),x-=x&-x;return tmp;
}
int main(){
    freopen("bzoj3173.in","r",stdin);
    freopen("bzoj3173.out","w",stdout);
    n=read();build(1,1,n);int ans=0;
    for (int i=1;i<=n;++i) x[i]=read()+1;
    for (int i=n;i;--i) rk[i]=query(1,1,n,x[i]);
//  for (int i=1;i<=n;++i) printf("%d ",rk[i]);
    for (int i=1;i<=n;++i){static int tmp;
        tmp=qr(rk[i]-1);++tmp;ans=max(ans,tmp);printf("%d\n",ans);add(rk[i],tmp);
    }
    return 0;
}