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

2015年1月29日8,1116

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

X0等于0 ,我们将1插入到位置0得到序列{1}
X1等于0 ,我们将1插入到位置0得到序列{2,1}
X2等于2 ,我们将1插入到位置0得到序列{2,1,3}
数据范围
30%„的数据 n<=1000
100%的数据 n<=100000

题解

题解

用treap维护序列后直接求lis

 

 

avatar
5 Comment threads
1 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
3 Comment authors
伪日常系LordNanoApe魔法炮orzwzh Recent comment authors
  Subscribe  
提醒
伪日常系LordNanoApe

第74行的判断好像并没有什么用。。。

huanghongxun

根据upper_bound的定义好像mn 可以直接赋为v 呢。。

huanghongxun

if(mn[t-1]<=v )
好像这句没用吧= =

翁家翌

神犇求加友链

orzwzh

神犇求加友链

魔法炮

跪!!