#P3173. [Tjoi2013]最长上升子序列

    ID: 2349 传统题 1000ms 512MiB 尝试: 2977 已通过: 987 难度: 6 上传者: 标签>CF1900普及+/提高-逆向还原操作树状数组倍增求第 k 小最长上升子序列线性 DP树状数组

[Tjoi2013]最长上升子序列

[TJOI2013] 最长上升子序列

题目描述

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

输入格式

第一行一个整数 NN,表示我们要将 11 到 NN 插入序列中。

接下是 NN 个数字,第 kk 个数字 XkX_k,表示我们将 kk 插入到位置 Xk(0≤Xk≤k−1,1≤k≤N)X_k(0\le X_k\le k-1,1\le k\le N)

输出格式

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

样例 #1

样例输入 #1

3
0 0 2

样例输出 #1

1
1
2

提示

100%100\% 的数据 n≤105n\le10^5。