Max

题目描述

我们有一个整数的多重集合 $S$，初始时为空。 给定 $Q$ 个查询，按顺序处理它们。 每个查询是下列类型之一。

$1\ x$：向 $S$ 中插入一个 $x$。

$2\ x\ c$：从 $S$ 中删除 $x$ 共 $m$ 次，其中 $m = \mathrm{min}(c,($ $S$ 中包含的 $x$ 的个数$))$。

$3$：打印 $($ $S$ 的最大值$)-($ $S$ 的最小值$)$。 当此查询给出时，保证 $S$ 非空。

输入格式

输入按以下格式从标准输入给出： $Q$ $\mathrm{query}_1$ $\vdots$ $\mathrm{query}_Q$

$\mathrm{query}_i$，表示第 $i$ 个查询，格式为下列之一： $1$ $x$

$2$ $x$ $c$

$3$

输出格式

按给定顺序换行输出类型 $3$ 查询的答案。

8
1 3
1 2
3
1 2
1 7
3
2 2 3
3

1
5
4

提示

$1 \leq Q \leq 2\times 10^5$ $0 \leq x \leq 10^9$ $1 \leq c \leq Q$ 当给出类型 $3$ 的查询时，$S$ 非空。 输入中的所有数值均为整数。多重集合 $S$ 的变化如下。

第 $1$ 个查询：向 $S$ 插入 $3$。 现在 $S$ 为 $\lbrace 3 \rbrace$。 第 $2$ 个查询：向 $S$ 插入 $2$。 现在 $S$ 为 $\lbrace 2, 3 \rbrace$。 第 $3$ 个查询：$S = \lbrace 2, 3\rbrace$ 的最大值为 $3$，最小值为 $2$，所以输出 $3-2=1$。 第 $4$ 个查询：向 $S$ 插入 $2$。 现在 $S$ 为 $\lbrace 2,2,3 \rbrace$。 第 $5$ 个查询：向 $S$ 插入 $7$。 现在 $S$ 为 $\lbrace 2, 2,3, 7\rbrace$。 第 $6$ 个查询：$S = \lbrace 2,2,3, 7\rbrace$ 的最大值为 $7$，最小值为 $2$，所以输出 $7-2=5$。 第 $7$ 个查询：由于 $S$ 中有两个 $2$ 且 $\mathrm{min(2,3)} = 2$，从 $S$ 中删除 $2$ 两次。 现在 $S$ 为 $\lbrace 3, 7\rbrace$。 第 $8$ 个查询：$S = \lbrace 3, 7\rbrace$ 的最大值为 $7$，最小值为 $3$，所以输出 $7-3=4$。
如果给定的查询中不包含类型 $3$ 的查询，则不应输出任何内容。

标签: AtCoder|abc253C

来源

AtCoder|abc253C