Balls and Pockets

题面翻译

题目翻译

给出一个无限长的序列 $p_0,p_1,p_2,\ldots$，初始 $p_i=i$。

给出 $n$ 个互不相同的整数 $a_1,a_2,\ldots,a_n$，可以对序列 $p$ 做以下操作若干次：

• 将序列 $p$ 的第 $a_1,a_2,\ldots,a_n$ 项从序列 $p$ 中删掉，然后将剩余的数字按照原来在序列 $p$ 中的顺序重新排列作为新的序列 $p$。

举个栗子：初始序列为 0 1 2 3 4 5 6 7 8 9...，$a = \{1,3,4\}$，那么

• 经过 1 次操作后序列变为 0 2 5 6 7 8 9 10 11 12...；

• 经过 2 次操作后序列变为 0 5 8 9 10 11 12 13 14 15...……

给出 $m$ 组询问，每组询问给出两个整数 $x,k$，询问进行 $k$ 次操作后的序列 $p$ 中 $p_x$ 的值。

输入格式

第一行两个整数 $m,n(1 \leq m,n \leq 10^5)$，

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n(0 \leq a_1 < \ldots < a_n \leq 10^9)$。

接下来 $m$ 行每行两个整数 $x_i,k_i(0 \leq x_i,k_i \leq 10^9)$ 描述一组询问。

输出格式

$m$ 行，每行一个整数表示对应询问答案。

题目描述

There is a strip with an infinite number of cells. Cells are numbered starting with $ 0 $ . Initially the cell $ i $ contains a ball with the number $ i $ .

There are $ n $ pockets located at cells $ a_1, \ldots, a_n $ . Each cell contains at most one pocket.

Filtering is the following sequence of operations:

• All pockets at cells $ a_1, \ldots, a_n $ open simultaneously, which makes balls currently located at those cells disappear. After the balls disappear, the pockets close again.
• For each cell $ i $ from $ 0 $ to $ \infty $ , if the cell $ i $ contains a ball, we move that ball to the free cell $ j $ with the lowest number. If there is no free cell $ j < i $ , the ball stays at the cell $ i $ .

Note that after each filtering operation each cell will still contain exactly one ball.

For example, let the cells $ 1 $ , $ 3 $ and $ 4 $ contain pockets. The initial configuration of balls is shown below (underscores display the cells with pockets):

0 1 2 3 4 5 6 7 8 9 ... After opening and closing the pockets, balls 1, 3 and 4 disappear:

0 2 5 6 7 8 9 ... After moving all the balls to the left, the configuration looks like this:

0 2 5 6 7 8 9 10 11 12 ... Another filtering repetition results in the following:

0 5 8 9 10 11 12 13 14 15 ... You have to answer $ m $ questions. The $ i $ -th of these questions is "what is the number of the ball located at the cell $ x_i $ after $ k_i $ repetitions of the filtering operation?"

输入格式

The first line contains two integers $ n $ and $ m $ — the number of pockets and questions respectively ( $ 1 \leq n, m \leq 10^5 $ ).

The following line contains $ n $ integers $ a_1, \ldots, a_n $ — the numbers of cells containing pockets ( $ 0 \leq a_1 < \ldots < a_n \leq 10^9 $ ).

The following $ m $ lines describe questions. The $ i $ -th of these lines contains two integers $ x_i $ and $ k_i $ ( $ 0 \leq x_i, k_i \leq 10^9 $ ).

输出格式

Print $ m $ numbers — answers to the questions, in the same order as given in the input.

样例 #1

样例输入 #1

3 15
1 3 4
0 0
1 0
2 0
3 0
4 0
0 1
1 1
2 1
3 1
4 1
0 2
1 2
2 2
3 2
4 2

样例输出 #1

0
1
2
3
4
0
2
5
6
7
0
5
8
9
10

down_