← 返回题目列表

Codeforces · 264/E

E. 路边树

中文机器翻译题面 查看原题

松鼠利斯喜欢坚果。利斯要求你种植一些坚果树。

沿街道有n个位置(从西到东编号为1到n)可以种植一棵树。树木每月生长一米。在每个月初,您应该处理一个查询。查询是以下类型之一:

1. 在位置 p 处种植一棵高度为 h 的树。
2. 从西边砍掉第 x 棵现存(未砍伐)树(其中 x 的索引为 1)。当我们砍伐树木时,它会掉落并占据其原来所在位置的所有可用位置。所以这个位置不能再种树了。

处理完每个查询后,您应该打印最长递增子序列的长度。如果集合中树的高度严格地从西向东递增(例如,集合中最西边的树必须是集合中最矮的树),则现有树的子集称为递增子序列。递增子序列的长度就是其中的树数。

请注意,Liss 不喜欢具有相同高度的树,因此可以保证任何时候都没有两棵树具有完全相同的高度。

输入

第一行包含两个整数:n 和 m (1 ≤ n ≤ 105; 1 ≤ m ≤ 2·105) — 位置数和查询数。

接下来的m行包含以下格式的查询信息:

- 如果第 i 个查询是类型 1,则第 i 行包含三个整数:1、pi 和 hi(1 ≤ pi ≤ n, 1 ≤ hi ≤ 10),其中 pi 是新树的位置,hi 是新树的初始高度。
- 如果第 i 个查询是类型 2,则第 i 行包含两个整数:2 和 xi (1 ≤ xi ≤ 10),其中 xi 是我们要切割的树的索引。

保证输入正确,即

- 对于类型 1 查询,pi 将成对不同。
- 对于类型 2 查询,xi 将小于或等于当前树的数量。
- 任何时候都没有两棵树具有完全相同的高度。

在每一行中,整数之间用单个空格分隔。

输出

打印 m 个整数 — 每次查询后最长递增子序列的长度。用空格分隔数字。

示例

输入 #1

4 6
1 1 1
1 4 4
1 3 4
2 2
1 2 8
2 3

输出 #1

1
2
3
2
2
2

注意

每次查询后您可以在以下动画中看到街道状态:

如果您的浏览器不支持动画 png,请在此处查看 gif 版本:http://212.193.37.254/codeforces/images/162/roadtree.gif