AT_abc241_d [ABC241D] Sequence Query
题目描述
有一个初始为空的序列 A。给定 q 次操作,每次操作是以下三种之一:
∙第一种操作给出一个整数 x,表示向 A 中插入一个 x;
∙第二种操作给出两个整数 x,k,表示将 A 中所有不超过 x 的元素从大到小排列,输出其中第 k 个;若这样的元素不足 k 个,输出 −1;
∙第三种操作给出两个整数 x,k,表示将 A 中所有不小于 x 的元素从小到大排列,输出其中第 k 个;若这样的元素不足 k 个,输出 −1。
输入格式
第一行输入一个整数 q(1≦q≦2×105) 代表操作次数。
此后 q 行,第 i 行先输入一个整数 ti(1≦ti≦3) 代表第 i 次操作的类型,随后在同一行:
∙若 ti=1,输入一个整数 xi(1≦xi≦1018) 代表插入的元素;
∙若 ti=2 或 ti=3,输入两个整数 $x_i, k_i \left(1 \leqq x_i \leqq 10^{18};\ 1 \leqq k_i \leqq 5\right)$,含义同题干。
输出格式
对于每次第二种或第三种操作,新起一行输出一个整数代表答案。所有答案按操作的先后顺序输出。
测试样例
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 解释
前四次操作依次插入 20,10,30,20,此时 A={20,10,30,20}。此后:
∙第 5 次操作:不小于 15 的元素为 {20,20,30},从小到大第 1 个是 20;
∙第 6 次操作:不小于 15 的元素从小到大第 2 个是 20;
∙第 7 次操作:不小于 15 的元素从小到大第 3 个是 30;
∙第 8 次操作:不小于 15 的元素只有 3 个,不足 4 个,输出 −1;
∙第 9 次操作:不超过 100 的元素只有 4 个,不足 5 个,输出 −1;
∙第 10 次操作:插入 1,此时 A={20,10,30,20,1};
∙第 11 次操作:不超过 100 的元素为 {20,10,30,20,1},从大到小第 5 个是 1。
7
1 7
1 2
1 7
2 7 2
3 2 1
2 8 3
3 2 2
7
2
2
7
样例 2 解释
前三次操作插入 7,2,7,此时 A={7,2,7}。此后:
∙不超过 7 的元素为 {2,7,7},从大到小第 2 个是 7;
∙不小于 2 的元素为 {2,7,7},从小到大第 1 个是 2;
∙不超过 8 的元素为 {2,7,7},从大到小第 3 个是 2;
∙不小于 2 的元素为 {2,7,7},从小到大第 2 个是 7。
提示
对于 100% 的数据,1≦q≦2×105,1≦xi≦1018,1≦ki≦5。所有输入均为整数。