#P51584. 「LOJ」 可持久化最长不降子序列
「LOJ」 可持久化最长不降子序列
题目描述
现给出两个操作:
-
操作: 在序列末尾加上一个非负整数
-
操作: 给出 ,回到第 次 操作之后的版本 ,将第 次 操作之后的版本全部删除
给出 ,表示操作的总次数
每一次操作后,输出当前版本的最长不降子序列的长度
输入格式
第一行一个整数 。
之后的 行,每行 个整数,表示 、。
当 为 时 ,表示 操作
当 为 时 ,表示 操作
输出格式
共 行,表示每一次操作后的最长不降子序列的长度
样例
5
0 2
0 0
1 0
1 0
0 5
1
1
0
0
1
第一次操作后,序列为[2]
第二次操作后,序列为[2,0]
第三次操作后,序列为[空]
第四次操作后,序列为[空]
第五次操作后,序列为[5]
数据范围与提示
对于数据点编号 ,;
对于数据点编号 ,;
对于数据点编号 ,;
对于数据点编号 ,,保证仅有 操作;
对于数据点编号 ,;
对于 的数据,满足
数据保证对于每一次 操作的 ,当前版本 均满足