#ABC241D. 区间询问

区间询问

AT_abc241_d [ABC241D] Sequence Query

题目描述

\hspace{15pt}有一个初始为空的序列 AA。给定 qq 次操作,每次操作是以下三种之一:

∙ \hspace{23pt}\bullet\,第一种操作给出一个整数 xx,表示向 AA 中插入一个 xx;

∙ \hspace{23pt}\bullet\,第二种操作给出两个整数 x,kx, k,表示将 AA 中所有不超过 xx 的元素从大到小排列,输出其中第 kk 个;若这样的元素不足 kk 个,输出 −1-1;

∙ \hspace{23pt}\bullet\,第三种操作给出两个整数 x,kx, k,表示将 AA 中所有不小于 xx 的元素从小到大排列,输出其中第 kk 个;若这样的元素不足 kk 个,输出 −1-1。

输入格式

\hspace{15pt}第一行输入一个整数 q(1≦q≦2×105)q \left(1 \leqq q \leqq 2 \times 10^5\right) 代表操作次数。

\hspace{15pt}此后 qq 行,第 ii 行先输入一个整数 ti(1≦ti≦3)t_i \left(1 \leqq t_i \leqq 3\right) 代表第 ii 次操作的类型,随后在同一行:

∙ \hspace{23pt}\bullet\,若 ti=1t_i = 1,输入一个整数 xi(1≦xi≦1018)x_i \left(1 \leqq x_i \leqq 10^{18}\right) 代表插入的元素;

∙ \hspace{23pt}\bullet\,若 ti=2t_i = 2 或 ti=3t_i = 3,输入两个整数 $x_i, k_i \left(1 \leqq x_i \leqq 10^{18};\ 1 \leqq k_i \leqq 5\right)$,含义同题干。

输出格式

\hspace{15pt}对于每次第二种或第三种操作,新起一行输出一个整数代表答案。所有答案按操作的先后顺序输出。

测试样例

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 解释

\hspace{15pt}前四次操作依次插入 20,10,30,2020, 10, 30, 20,此时 A={20,10,30,20}A = \{20, 10, 30, 20\}。此后:

∙ \hspace{23pt}\bullet\,第 55 次操作:不小于 1515 的元素为 {20,20,30}\{20, 20, 30\},从小到大第 11 个是 2020;

∙ \hspace{23pt}\bullet\,第 66 次操作:不小于 1515 的元素从小到大第 22 个是 2020;

∙ \hspace{23pt}\bullet\,第 77 次操作:不小于 1515 的元素从小到大第 33 个是 3030;

∙ \hspace{23pt}\bullet\,第 88 次操作:不小于 1515 的元素只有 33 个,不足 44 个,输出 −1-1;

∙ \hspace{23pt}\bullet\,第 99 次操作:不超过 100100 的元素只有 44 个,不足 55 个,输出 −1-1;

∙ \hspace{23pt}\bullet\,第 1010 次操作:插入 11,此时 A={20,10,30,20,1}A = \{20, 10, 30, 20, 1\};

∙ \hspace{23pt}\bullet\,第 1111 次操作:不超过 100100 的元素为 {20,10,30,20,1}\{20, 10, 30, 20, 1\},从大到小第 55 个是 11。

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

样例 2 解释

\hspace{15pt}前三次操作插入 7,2,77, 2, 7,此时 A={7,2,7}A = \{7, 2, 7\}。此后:

∙ \hspace{23pt}\bullet\,不超过 77 的元素为 {2,7,7}\{2, 7, 7\},从大到小第 22 个是 77;

∙ \hspace{23pt}\bullet\,不小于 22 的元素为 {2,7,7}\{2, 7, 7\},从小到大第 11 个是 22;

∙ \hspace{23pt}\bullet\,不超过 88 的元素为 {2,7,7}\{2, 7, 7\},从大到小第 33 个是 22;

∙ \hspace{23pt}\bullet\,不小于 22 的元素为 {2,7,7}\{2, 7, 7\},从小到大第 22 个是 77。

提示

\hspace{15pt}对于 100%100\% 的数据,1≦q≦2×1051 \leqq q \leqq 2 \times 10^5,1≦xi≦10181 \leqq x_i \leqq 10^{18},1≦ki≦51 \leqq k_i \leqq 5。所有输入均为整数。