Bzoj 3173: [Tjoi2013]最长上升子序列平衡树,Treap,二分,树的序遍历

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

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

Source

题解：Treap+中序遍历+二分。先把所有数字加入，这用平衡树维护即可(但要记得加入的是位置)。然后中序遍历搞出最终序列。最后二分求最长上升子序列。(其实就是nlogn的求法)

 #include<bits/stdc++.h>
 using namespace std;
 #define MAXN 100010
 #define INF 1e9
 struct node
 {
     int left,right,val,size,count,rnd;
 }tree[MAXN];
 int ans[MAXN],v[MAXN],a[MAXN],SIZE,root,lv;
 int read()
 {
     int s=,fh=;char ch=getchar();
     while(ch<''||ch>''){if(ch=='-')fh=-;ch=getchar();}
     while(ch>=''&&ch<=''){s=s*+(ch-'');ch=getchar();}
     return s*fh;
 }
 void Update(int k){tree[k].size=tree[tree[k].left].size+tree[tree[k].right].size+;}
 void Lturn(int &k){int t=tree[k].right;tree[k].right=tree[t].left;tree[t].left=k;tree[t].size=tree[k].size;Update(k);k=t;}
 void Rturn(int &k){int t=tree[k].left;tree[k].left=tree[t].right;tree[t].right=k;tree[t].size=tree[k].size;Update(k);k=t;}
 void Insert(int &k,int x)
 {
     if(k==)
     {
         SIZE++;k=SIZE;
         tree[k].size=;tree[k].rnd=rand();
         return;
     }
     tree[k].size++;
     if(x<=tree[tree[k].left].size){Insert(tree[k].left,x);if(tree[tree[k].left].rnd<tree[k].rnd)Rturn(k);}
     else {Insert(tree[k].right,x-tree[tree[k].left].size-);if(tree[tree[k].right].rnd<tree[k].rnd)Lturn(k);}
 }
 void dfs(int k)
 {
     if(k==)return;
     dfs(tree[k].left);
     v[++lv]=k;
     dfs(tree[k].right);
 }
 int main()
 {
     int n,i,la,tmp,x;
     n=read();
     for(i=;i<=n;i++){x=read();Insert(root,x);}
     lv=;
     dfs(root);
     memset(ans,,sizeof(ans));
     la=;
     for(i=;i<=n;i++)a[i]=INF;
     for(i=;i<=n;i++)
     {
         tmp=upper_bound(a+,a+la+,v[i])-a;
         a[tmp]=min(a[tmp],v[i]);
         ans[v[i]]=tmp;
         la=max(la,tmp);
     }
     for(i=;i<=n;i++)
     {
         ans[i]=max(ans[i-],ans[i]);
         printf("%d\n",ans[i]);
     }
     return ;
 }