AT_abc205_d [ABC205D] Kth Excluded

题目描述

给定一个长度为 $N$ 的正整数序列 $A = (A_1, A_2, \dots, A_N)$，以及 $Q$ 个查询。

对于第 $i$ 个查询（$1 \leq i \leq Q$），给定一个正整数 $K_i$，请你求出所有与 $A_1, A_2, \dots, A_N$ 都不相等的正整数中，从小到大排列后第 $K_i$ 个数。

输入格式

输入从标准输入中按以下格式给出。

$N$ $Q$
$A_1$ $A_2$ $\ldots$ $A_N$
$K_1$
$K_2$
$\vdots$
$K_Q$

输出格式

输出共 $Q$ 行。第 $i$ 行输出第 $i$ 个查询的答案。

输入输出样例 #1

输入 #1

4 3
3 5 6 7
2
5
3

输出 #1

2
9
4

输入输出样例 #2

输入 #2

5 2
1 2 3 4 5
1
10

输出 #2

6
15

说明/提示

限制条件

• $1 \leq N, Q \leq 10^5$
• $1 \leq A_1 < A_2 < \dots < A_N \leq 10^{18}$
• $1 \leq K_i \leq 10^{18}$
• 输入均为整数。

样例解释 1

与 $3, 5, 6, 7$ 都不相等的正整数按升序排列为 $1, 2, 4, 8, 9, 10, 11, \dots$。从小到大第 $2$ 个、第 $5$ 个、第 $3$ 个分别为 $2, 9, 4$。

由 ChatGPT 4.1 翻译