「BZOJ3173」[TJOI2013]最长上升子序列

Description

给定一个序列,初始为空。现在我们将11NN的数字插入到序列中,每次将一个数字插入到一个特定的位置。每插入一个数字,我们都想知道此时最长上升子序列长度是多少?

Input

第一行一个整数NN,表示我们要将11NN插入序列中,接下是NN个数字,第kk个数字XkX_k,表示我们将kk插入到位置Xk(0Xkk1,1kN)X_k(0\leq X_k\leq k-1,1\leq k\leq N)

Outpu t

NN行,第ii行表示ii插入XiX_i位置后序列的最长上升子序列的长度是多少。

Sample Input

1
2
3
0 0 2

Sample Output

1
2
3
1
1
2

HINT

100%100\%的数据 n100000n\leq 100000

Solution

每一次都是插入最大值,那么在一个地方插入,以他结尾的最长上升子序列长度为前缀最大值+1+1

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
#define rt ch[0][1]
const int N = 120000;
int n;
int fa[N], ch[N][2], tot;
bool ident(int x) {
return ch[fa[x]][1] == x;
}
void con(int x, int F, int how) {
ch[F][how] = x;
fa[x] = F;
}
int siz[N], mx[N], val[N];
void up(int x) {
siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + 1;
mx[x] = max(max(mx[ch[x][0]], mx[ch[x][1]]), val[x]);
}
void rotate(int x) {
if(ident(x)) {
int y = fa[x];
int z = ch[x][0];
con(x, fa[y], ident(y));
con(y, x, 0);
con(z, y, 1);
up(y); up(x);
} else {
int y = fa[x];
int z = ch[x][1];
con(x, fa[y], ident(y));
con(y, x, 1);
con(z, y, 0);
up(y); up(x);
}
}
void splay(int x, int to) {
to = fa[to];
for(int y = fa[x]; y != to; y = fa[x]) {
if(fa[y] != to) rotate(ident(y) == ident(x) ? y : x);
rotate(x);
}
}
void ins(int x, int v) {
if(!tot) {
rt = ++tot;
mx[tot] = val[tot] = v;
siz[tot] = 1;
return;
}
int p = rt;
while(p) {
if(siz[ch[p][0]] + 1 == x) {
int tmp = ch[p][1];
ch[p][1] = ++tot;
mx[tot] = val[tot] = v + 1;
fa[tot] = p;
siz[tot] = siz[tmp] + 1;
fa[tmp] = tot;
ch[tot][1] = tmp;
splay(tot,rt);
return;
}
if(siz[ch[p][0]] >= x) p = ch[p][0];
else x -= siz[ch[p][0]] + 1, p = ch[p][1];
}
}
int query(int x) {
int p = rt;
int ans = 0;
while(p) {
if(siz[ch[p][0]] + 1 == x) {
ans = max(ans, mx[ch[p][0]]);
ans = max(ans, val[p]);
return ans;
}
if(siz[ch[p][0]] >= x) p = ch[p][0];
else x -= siz[ch[p][0]] + 1, ans = max(ans, max(mx[ch[p][0]], val[p])), p = ch[p][1];
}
return ans;
}
int main() {
n = read();
ins(0, 0);
for(int i = 1; i <= n; ++i) {
int x = read() + 1;
ins(x, query(x));
writeln(mx[rt]);
}
return 0;
}