CF1227D2 Optimal Subsequences (Hard Version)

这是该问题的更难版本。在本版本中，$1 \le n, m \le 2\cdot10^5$。如果你锁定了本题，可以对其进行 hack。但只有在你同时锁定了两个问题时，才能对前一个问题进行 hack。 给定一个长度为 $n$ 的整数序列 $a=[a_1,a_2,\dots,a_n]$。其子序列可以通过从序列 $a$ 中移除零个或多个元素得到（这些元素不一定是连续的）。例如，对于序列 $a=[11,20,11,33,11,20,11]$： - $[11,20,11,33,11,20,11]$，$[11,20,11,33,11,20]$，$[11,11,11,11]$，$[20]$，$[33,20]$ 都是子序列（这里只列举了部分）； - $[40]$，$[33,33]$，$[33,20,20]$，$[20,20,11,11]$ 不是子序列。 假设还给定一个非负整数 $k$（$1 \le k \le n$），如果一个子序列满足以下条件，则称其为最优子序列： - 它的长度为 $k$，并且其元素之和在所有长度为 $k$ 的子序列中最大； - 在所有满足上述条件的长度为 $k$ 的子序列中，它在字典序上最小。 回忆一下，如果序列 $b=[b_1, b_2, \dots, b_k]$ 在第一个不同的位置 $t$（$1 \le t \le k$）满足 $b_t < c_t$，则称 $b$ 在字典序上小于 $c=[c_1, c_2, \dots, c_k]$。形式化地说：存在 $t$，使得 $b_1=c_1$，$b_2=c_2$，...，$b_{t-1}=c_{t-1}$，并且 $b_t < c_t$。例如： - $[10, 20, 20]$ 字典序小于 $[10, 21, 1]$， - $[7, 99, 99]$ 字典序小于 $[10, 21, 1]$， - $[10, 21, 0]$ 字典序小于 $[10, 21, 1]$。 现在给定序列 $a=[a_1,a_2,\dots,a_n]$ 和 $m$ 个询问，每个询问包含两个整数 $k_j$ 和 $pos_j$（$1 \le k_j \le n$，$1 \le pos_j \le k_j$）。对于每个询问，请输出对于 $k=k_j$ 时，$a$ 的最优子序列中第 $pos_j$ 个位置上的值。 例如，如果 $n=4$，$a=[10,20,30,20]$，$k_j=2$，则最优子序列为 $[20,30]$——它是在所有长度为 $2$ 且元素和最大的子序列中字典序最小的。因此，询问 $k_j=2$，$pos_j=1$ 的答案是 $20$，$k_j=2$，$pos_j=2$ 的答案是 $30$。

第一行包含一个整数 $n$（$1 \le n \le 2\cdot10^5$）——序列 $a$ 的长度。 第二行包含序列 $a$ 的元素：整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）。 第三行包含一个整数 $m$（$1 \le m \le 2\cdot10^5$）——询问的数量。 接下来的 $m$ 行，每行包含一对整数 $k_j$ 和 $pos_j$（$1 \le k_j \le n$，$1 \le pos_j \le k_j$）——表示一次询问。

输出 $m$ 个整数 $r_1, r_2, \dots, r_m$，每行一个，表示每个询问的答案。$r_j$ 应等于对于 $k=k_j$ 时最优子序列的第 $pos_j$ 个位置上的值。

在第一个样例中，对于 $a=[10,20,10]$，最优子序列为： - 当 $k=1$ 时：$[20]$； - 当 $k=2$ 时：$[10,20]$； - 当 $k=3$ 时：$[10,20,10]$。 由 ChatGPT 4.1 翻译