A6904 | 序列查询
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
有一个一开始为空的序列 $序列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$
- $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$
样例解释
前 $4$ 次插入后，$序列A$ 里有：$[20,10,30,20]$。
接下来做 $3\ 15\ k$：只看 $\ge 15$ 的数，就是 $[20,30,20]$。
把它从小到大排成数组 $B$：$B=[20,20,30]$（下标从 $1$ 开始）
从大到小排成 $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$。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？