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

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 2009 Solved: 1023
[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

0 0 2
Sample Output

2
HINT

100%的数据 n<=100000

solution: treap+Lis

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 7;
inline int randa(){int seed=914;return seed=int(seed*28741LL%2147483641);
}
struct Treap{int ls, rs, sz, rd;
}tr[N<<1];
int cnt, root, a[N], ans[N], tot, len, ret[N];
void pushup(int nd){tr[nd].sz=tr[tr[nd].ls].sz+tr[tr[nd].rs].sz+1;
}
void lrot(int &nd){int t=tr[nd].rs;tr[nd].rs=tr[t].ls; tr[t].ls=nd; pushup(nd); pushup(t); nd=t;
}
void rrot(int &nd){int t=tr[nd].ls;tr[nd].ls=tr[t].rs; tr[t].rs=nd; pushup(nd); pushup(t); nd=t;
}
void insert(int &nd, int k){if( nd==0 ){ nd=++cnt; tr[nd].sz=1; tr[nd].rd=randa(); return ; }tr[nd].sz++;if( tr[tr[nd].ls].sz>=k ) {insert(tr[nd].ls, k); if(tr[tr[nd].ls].rd>tr[nd].rd ) rrot(nd); }else { insert(tr[nd].rs, k-tr[tr[nd].ls].sz-1 ); if(tr[tr[nd].rs].rd>tr[nd].rd ) lrot(nd); }
}
void dfs(int nd){if( nd==0 ) return ;dfs(tr[nd].ls);a[++tot]=nd;dfs(tr[nd].rs);
}
int main(){int n, x;scanf("%d", &n );root=cnt=0;for ( int i=1; i<=n; i++ ) scanf("%d", &x ), insert(root, x);tot=0;dfs(root);//for ( int i=1; i<=n; i++ ) printf("%d ", a[i] );//printf("\n");len=1;ans[1]=a[1];ret[a[1]]=1;for ( int i=2; i<=n; i++ ){if( a[i]>ans[len] ) ans[++len]=a[i], ret[a[i]]=len;else {int t=lower_bound(ans+1,ans+1+len,a[i])-ans;ans[t]=a[i];ret[a[i]]=t;}}for ( int i=1; i<=n; i++ ){ret[i]=max(ret[i],ret[i-1]);printf("%d\n", ret[i]);}}

BZOJ3173[最长上升子序列] Treap+LIS

solution: treap+Lis