3173: [Tjoi2013]最长上升子序列
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 2253 Solved: 1136
[Submit][Status][Discuss]
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<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define ll long long
#define N 100050
using 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]]<k){
insert(rs[u],k-siz[ls[u]]-1);
if(rd[rs[u]]<rd[u])lturn(u);
}
else{
insert(ls[u],k);
if(rd[ls[u]]<rd[u])rturn(u);
}
}
void dfs(int x){
if(!x)return;
dfs(ls[x]);
a[++num]=x;
dfs(rs[x]);
}
void solve(){
int tot=0;
memset(b,0x3f,sizeof(b));
for(int i=1;i<=n;i++){
int p=lower_bound(b+1,b+1+n,a[i])-b;
if(p>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;
}