Steven_MengのBlog

传送门
注意:$X_k$为位置,而$k$才是真正加进去的数。

加入的序列为$1,2,3,……$
也就是说,每次加入的数都是当前最大的。
那么我们很快就可以推出$dp$方程:
$dp[i]=max(dp[i],dp[j]+1) j<i$
$dp[i]$初始值为$1$

我们发现:插入一个数的时候,只要知道$max(dp[j]+1)$,也就是$max(dp[j])+1$,就可以完成维护。
所以,我们建立一棵维护$dp$值的$FHQTreap$,每次加入数时,取左子树$dp$最大值$+1$插入平衡树.
输出时输出根节点$dp$值即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
// luogu-judger-enable-o2
#include <bits/stdc++.h>
#define MAXN 1000005
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return x*f;
}
int a[MAXN];
namespace FHQTreap{
struct node{
int l,r;
int val;//dp值
int pri;//优先级(随机生成)
int id;//下标
int sz;
}tree[MAXN];
#define lc(i) tree[i].l
#define rc(i) tree[i].r
int tot;
inline void Update(int x){
tree[x].sz=tree[lc(x)].sz+tree[rc(x)].sz+1;
tree[x].val=max(max(tree[lc(x)].val,tree[rc(x)].val),a[tree[x].id]);
}
inline int New(int v,int id){
a[id]=v;
tree[++tot].val=v,tree[tot].pri=rand(),tree[tot].sz=1,tree[tot].id=id;
return tot;
}
int Merge(int x,int y){
if (!x||!y) return x+y;
if (tree[x].pri<tree[y].pri){
rc(x)=Merge(rc(x),y),Update(x);
return x;
}
else{
lc(y)=Merge(x,lc(y)),Update(y);
return y;
}
}
void Split(int i,int k,int &x,int &y){
if (!i) {
x=y=0;
}
else {
if (tree[lc(i)].sz>=k) {y=i,Split(lc(i),k,x,lc(i));}
else {x=i,Split(rc(i),k-tree[lc(i)].sz-1,rc(i),y);}
Update(i);
}
}
int root;
#undef lc
#undef rc
}
using namespace FHQTreap;
int main(){
int n=read();
for (register int i=1;i<=n;++i){
int pos=read();
int x=0,y=0;
Split(root,pos,x,y);
x=Merge(x,New(tree[x].val+1,i));
root=Merge(x,y);
printf("%d\n",tree[root].val);
}
}

 评论