A6904. 序列查询
编程题
普及/提高-
知识点
题目描述
有一个一开始为空的序列 $序列A$（可以理解成一个“袋子”，里面的数允许重复）。
一共有 $Q$ 次操作，每次操作是下面三种之一：
1. $1\ x$：把数字 $x$ 放进 $序列A$ 里（插入一个 $x$）。
2. $2\ x\ k$：只看 $序列A$ 里所有满足 $\le x$ 的数字，把它们从大到小排好，输出第 $k$ 个（第 $k$ 大）。如果不够 $k$ 个，输出 $-1$。
3. $3\ x\ k$：只看 $序列A$ 里所有满足 $\ge x$ 的数字，把它们从小到大排好，输出第 $k$ 个（第 $k$ 小）。如果不够 $k$ 个，输出 $-1$。
一共有 $Q$ 次操作，每次操作是下面三种之一：
1. $1\ x$：把数字 $x$ 放进 $序列A$ 里（插入一个 $x$）。
2. $2\ x\ k$：只看 $序列A$ 里所有满足 $\le x$ 的数字，把它们从大到小排好，输出第 $k$ 个（第 $k$ 大）。如果不够 $k$ 个，输出 $-1$。
3. $3\ x\ k$：只看 $序列A$ 里所有满足 $\ge x$ 的数字，把它们从小到大排好，输出第 $k$ 个（第 $k$ 小）。如果不够 $k$ 个，输出 $-1$。
输入格式
第一行一个整数 $Q$。
接下来 $Q$ 行，每行是一次操作（格式如上）。
接下来 $Q$ 行，每行是一次操作（格式如上）。
输出格式
遇到操作 $2$ 或 $3$ 时，输出一行答案。
输入输出样例
输入 #1
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
输出 #1
20 20 30 -1 -1 1
说明/提示
## 数据范围
- $1\le Q\le 2\times 10^5$
- $1\le x\le 10^{18}$
- $1\le k\le 5$
## 样例解释
前 $4$ 次插入后，$序列A$ 里有：$[20,10,30,20]$。
接下来做 $3\ 15\ k$：只看 $\ge 15$ 的数，就是 $[20,30,20]$。
把它从小到大排成数组 $B$：$B=[20,20,30]$（下标从 $1$ 开始）
- $3\ 15\ 1$：要第 $1$ 小，$B_1=20$
- $3\ 15\ 2$：要第 $2$ 小，$B_2=20$
- $3\ 15\ 3$：要第 $3$ 小，$B_3=30$
- $3\ 15\ 4$：要第 $4$ 小，但 $B$ 只有 $3$ 个数，所以输出 $-1$
再做 $2\ 100\ 5$：只看 $\le 100$ 的数，其实就是全部 $[20,10,30,20]$。
从大到小排成 $C=[30,20,20,10]$，只有 $4$ 个数，要第 $5$ 大，不存在，所以输出 $-1$。
然后插入 $1$，现在 $序列A=[20,10,30,20,1]$。
再次做 $2\ 100\ 5$：从大到小排成 $C=[30,20,20,10,1]$，第 $5$ 大是 $C_5=1$，所以输出 $1$。
- $1\le Q\le 2\times 10^5$
- $1\le x\le 10^{18}$
- $1\le k\le 5$
## 样例解释
前 $4$ 次插入后，$序列A$ 里有：$[20,10,30,20]$。
接下来做 $3\ 15\ k$：只看 $\ge 15$ 的数，就是 $[20,30,20]$。
把它从小到大排成数组 $B$：$B=[20,20,30]$（下标从 $1$ 开始）
- $3\ 15\ 1$：要第 $1$ 小，$B_1=20$
- $3\ 15\ 2$：要第 $2$ 小，$B_2=20$
- $3\ 15\ 3$：要第 $3$ 小，$B_3=30$
- $3\ 15\ 4$：要第 $4$ 小，但 $B$ 只有 $3$ 个数，所以输出 $-1$
再做 $2\ 100\ 5$：只看 $\le 100$ 的数，其实就是全部 $[20,10,30,20]$。
从大到小排成 $C=[30,20,20,10]$，只有 $4$ 个数，要第 $5$ 大，不存在，所以输出 $-1$。
然后插入 $1$，现在 $序列A=[20,10,30,20,1]$。
再次做 $2\ 100\ 5$：从大到小排成 $C=[30,20,20,10,1]$，第 $5$ 大是 $C_5=1$，所以输出 $1$。