Sequence Query

题目描述

我们有一个空序列 $A$.
给定 $Q$ 个查询，按顺序处理它们。
每个查询属于以下三种类型之一。

$1 x$ ：将 $x$ 插入到 $A$ 中。

$2 x k$ ：在 $A$ 中不超过 $x$ 的元素中，输出第 $k$ 大的值。 ($k$ 不超过 $\bf{5}$)
如果在 $A$ 中不超过 $x$ 的元素少于 $k$ 个，则输出 $-1$。

$3 x k$ ：在 $A$ 中不小于 $x$ 的元素中，输出第 $k$ 小的值。 ($k$ 不超过 $\bf{5}$)
如果在 $A$ 中不小于 $x$ 的元素少于 $k$ 个，则输出 $-1$。

输入格式

输入按照标准输入给出，格式如下： $Q$ $\text{query}_1$ $\text{query}_2$ $\vdots$ $\text{query}_Q$

在第 $i$ 个查询 $\text{query}_i$ 中，首先给出查询的类型 $c_i$（它是 $1, 2$ 或 $3$ 之一）。
如果 $c_i=1$，则额外给出 $x$；如果 $c_i=2, 3$，则额外给出 $x$ 和 $k$。 换句话说，每个查询以以下三种格式之一给出：
$1$ $x$

$2$ $x$ $k$

$3$ $x$ $k$

输出格式

打印 $q$ 行，其中 $q$ 是满足 $c_i=2,3$ 的查询数量。
第 $j$ 行 $(1\leq j\leq q)$ 应包含第 $j$ 个此类查询的答案。

11
1 20
1 10
1 30
1 20
3 15 1
3 15 2
3 15 3
3 15 4
2 100 5
1 1
2 100 5

20
20
30
-1
-1
1

提示

$1\leq Q \leq 2\times 10^5$ $1\leq x\leq 10^{18}$ $1\leq k\leq 5$ 输入中的所有数值均为整数。在处理完 $\text{query}_{1,2,3,4}$ 后，我们有 $A=(20,10,30,20)$.
对于 $\text{query}_{5,6,7}$，$A$ 中不小于 $15$ 的元素为 $(20,30,20)$.
它们的第 $1$ 个最小值是 $20$；第 $2$ 个是 $20$；第 $3$ 个是 $30$.

标签: AtCoder|abc241D

来源

AtCoder|abc241D