#53. 可持久化最长不降子序列

内存限制:256 MiB 时间限制:500 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: finedev

题目描述

现给出两个操作:

  1. add 操作: 在序列末尾加上一个非负整数 x

  2. back 操作: 给出 x ,回到第 x add 操作之后的版本 ,将第 x add 操作之后的版本全部删除

给出 n ,表示操作的总次数

每一次操作后,输出当前版本的最长不降子序列的长度 len

输入格式

第一行一个整数 n

之后的 n 行,每行 2 个整数,表示 opt x

opt 0 时 ,表示 add 操作

opt 1 时 ,表示 back 操作

输出格式

n 行,表示每一次操作后的最长不降子序列的长度 len

样例

样例输入 1

5
0 2
0 0
1 0
1 0
0 5

样例输出 1

1
1
0
0
1

样例解释 1

第一次操作后,序列为[2]

第二次操作后,序列为[2,0]

第三次操作后,序列为[空]

第四次操作后,序列为[空]

第五次操作后,序列为[5]

数据范围与提示

对于数据点编号 1-4 n = 1000

对于数据点编号 5-6 n = 10000, x_i \le 10000

对于数据点编号 7-10 n = 499998

对于数据点编号 10-11 n = 499999 ,保证仅有 add 操作;

对于数据点编号 12-20 n = 500000

对于 100\% 的数据,满足 x_i \le 10000000

数据保证对于每一次 back 操作的 x_i ,当前版本 k 均满足 x_i \le k