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
|
#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;
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);
}
}
|
