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的求法)

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define MAXN 100010
 4 #define INF 1e9
 5 struct node
 6 {
 7     int left,right,val,size,count,rnd;
 8 }tree[MAXN];
 9 int ans[MAXN],v[MAXN],a[MAXN],SIZE,root,lv;
10 int read()
11 {
12     int s=0,fh=1;char ch=getchar();
13     while(ch<'0'||ch>'9'){if(ch=='-')fh=-1;ch=getchar();}
14     while(ch>='0'&&ch<='9'){s=s*10+(ch-'0');ch=getchar();}
15     return s*fh;
16 }
17 void Update(int k){tree[k].size=tree[tree[k].left].size+tree[tree[k].right].size+1;}
18 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;}
19 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;}
20 void Insert(int &k,int x)
21 {
22     if(k==0)
23     {
24         SIZE++;k=SIZE;
25         tree[k].size=1;tree[k].rnd=rand();
26         return;
27     }
28     tree[k].size++;
29     if(x<=tree[tree[k].left].size){Insert(tree[k].left,x);if(tree[tree[k].left].rnd<tree[k].rnd)Rturn(k);}
30     else {Insert(tree[k].right,x-tree[tree[k].left].size-1);if(tree[tree[k].right].rnd<tree[k].rnd)Lturn(k);}
31 }
32 void dfs(int k)
33 {
34     if(k==0)return;
35     dfs(tree[k].left);
36     v[++lv]=k;
37     dfs(tree[k].right);
38 }
39 int main()
40 {
41     int n,i,la,tmp,x;
42     n=read();
43     for(i=1;i<=n;i++){x=read();Insert(root,x);}
44     lv=0;
45     dfs(root);
46     memset(ans,0,sizeof(ans));
47     la=0;
48     for(i=1;i<=n;i++)a[i]=INF;
49     for(i=1;i<=n;i++)
50     {
51         tmp=upper_bound(a+1,a+la+1,v[i])-a;
52         a[tmp]=min(a[tmp],v[i]);
53         ans[v[i]]=tmp;
54         la=max(la,tmp);
55     }
56     for(i=1;i<=n;i++)
57     {
58         ans[i]=max(ans[i-1],ans[i]);
59         printf("%d
",ans[i]);
60     }
61     return 0;
62 }

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