BZOJ3173 — Click Here
Description
给定一个序列，初始为空。现在我们将1到N的数字插入到序列中，每次将一个数字插入到一个特定的位置。每插入一个数字，我们都想知道此时最长上升子序列长度是多少？
Input
第一行一个整数N，表示我们要将1到N插入序列中，接下是N个数字，第k个数字Xk，表示我们将k插入到位置Xk(0<=Xk<=k-1,1<=k<=N)
Output
N行，第i行表示i插入Xi位置后序列的最长上升子序列的长度是多少。
100%的数据，N<=100000
Solutions
注意到1-N是依次插入，因此后插入的数字不会影响到先插入的数字的答案。(或者说，每个数字的答案只由比它小的数字决定)
所以，只用利用Treap求出最后的序列，然后跑一次最长公共子序列(LIS)即可。由于N很大，还需要用单调队列优化。
CODE
CODE - Click Here