← 返回题目列表

AtCoder · abc451_c

F. 林下

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

分数: 300 点

问题陈述

高桥正在管理他花园里的树木数量。最初,花园里没有树木。

Q 查询按顺序给出。每个查询都是以下两种类型之一。处理每个查询后,立即输出花园中当前的树木数量。

  • 1 h : 添加一棵新树的高度 h 到花园。
  • 2 h : 移除花园中当前高度不超过的所有树木 h.

约束

  • 1 \le Q \le 3 \times 10^5
  • 1 \le h \le 10^9
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

\text{query}_i,代表 i-th 查询,是以下两种类型之一:

1 h
2 h

输出

输出 Q 行。

的 i- 第行应包含处理后立即花园中的树木数量 i- 第一个查询。


样本输入 1

5
1 5
1 7
1 8
2 7
1 3

示例输出 1

1
2
3
1
2

树的数量变化如下。

  • 一棵高树 添加了 5 。花园里有一棵高大的树 添加了 5.
  • 一棵高树 添加了 7 。花园里有两棵高大的树 添加了 5, 7.
  • 一棵高树 添加了 8 。花园里有三棵高树 5, 7, 8.
  • 树的高度最高 7 被删除。花园里有一棵高大的树 8.
  • 一棵高树 添加了 3 。花园里有两棵高大的树 添加了 8, 3.

示例输入 2

12
2 256601193
1 85138616
1 202564041
2 276477192
1 55551662
1 170271057
2 754166580
1 854388209
1 772036624
2 651124113
1 301137866
2 290875185

示例输出 2

0
1
2
0
1
2
0
1
2
2
3
3