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
76
77
78
79
80
81
82
83
84
85
86
| #include <cstdio>
#include <algorithm>
#include <vector>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
using namespace std;
typedef long long ll;
const int inf = 1 << 30;
const int maxn = 2e5 + 5;
const int N = 1e3 + 5;
const int base = 131;
struct node
{
int ls, rs, sizx, w, key, pos;
} tr[maxn];
int cnt, rt, dp[maxn], su = 1;
int rand()
{
su = (su * base) % 100007;
return su;
}
int newnode(int w, int i)
{
tr[++cnt].sizx = 1, tr[cnt].w = w;
tr[cnt].key = rand(), tr[cnt].pos = i, dp[i] = w;
return cnt;
}
void pushup(int now)
{
tr[now].sizx = tr[tr[now].ls].sizx + tr[tr[now].rs].sizx + 1;
tr[now].w = max(dp[tr[now].pos], max(tr[tr[now].ls].w, tr[tr[now].rs].w));
}
void split(int now, int big, int &x, int &y)
{
if (!now)
x = y = 0;
else
{
if (big <= tr[tr[now].ls].sizx)
y = now, split(tr[now].ls, big, x, tr[now].ls);
else
x = now, split(tr[now].rs, big - 1 - tr[tr[now].ls].sizx, tr[now].rs, y);
pushup(now);
}
}
int merge(int x, int y)
{
if (!x || !y)
return x + y;
else
{
if(tr[x].key>tr[y].key)
{
tr[x].rs=merge(tr[x].rs,y);
pushup(x);
return x;
}
else
{
tr[y].ls=merge(x,tr[y].ls);
pushup(y);
return y;
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n,big;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>big;
int x,y,z;
split(rt,big,x,y);
rt=merge(merge(x,newnode(tr[x].w+1,i)),y);
cout<<tr[rt].w<<endl;
}
}
|
