web analytics

BZOJ3173:[Tjoi2013]最长上升子序列 treap+LIS(nlogn)

3173: [Tjoi2013]最长上升子序列

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 1731  Solved: 892
[Submit][Status][Discuss]

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

100%的数据 n<=100000

分析:

如果光看这道题。这道题有很多很巧的地方。比如说插入的数字是连续的。插入的方式是有趣的。
按照题意。维护数列,这里就用的是平衡树。

最巧的地方就在于。由于插入序列是连续的。所以如果你用nlogn的方法。
存以当前数为结尾的LIS。
这样LIS就只用求一遍。
(实现看代码。)

Post a Comment

You must be logged in to post a comment.