题目背景
题目描述
空想用跳棋模拟「圣战」中机凯种的移动方式。
一条无限长的数轴上有 n 个不能动的跳棋,空会询问把一颗可以动的跳棋放在一个位置可以最多进行几次跳跃。空会问很多次,每次询问互相独立。
设第 i 颗不能动的棋子的坐标为 xi(∀i∈[1,n]).
则跳棋移动的规则如下:
- 这颗跳棋必须是允许移动的。
- 若这颗棋子位于 a,目标位置为 b,则应仅有一颗棋子位于二个位置之间且中间棋子到 a,b 的距离相等。
形式化的讲应有:
k=1∑n[xk∈[b,a]]=1且 ∃k xk=2a+b.
输入格式
第一行两个整数 n,q,同题意。
接下来一行 n 个整数,第 i 个表示 xi。
接下来一行 q 个数 x0,表示放置可以动的棋子的位置。
输出格式
q 行,每行一个整数,第 i 行表示第 i 次询问的结果。
提示
样例解释 1
□□■□■□□■□□从左到右的三个红色方块是询问的位置。
- 对于第一个询问,可以跳 1 步,从 4 跳到 2。
- 对于第二个询问,可以跳 2 步,从 6 跳到 4 跳到 2。
- 对于第三个询问,棋子不能向左移动,因为左边同距离位置有一颗不能动的棋子。
对于 100% 的数据满足 1≤n≤3×106,1≤q≤3×105,1≤x≤1018,xi+1<xi+1(∀i∈[1,n−1])。
Subtask 编号 |
n≤ |
q≤ |
时限 |
空间限制 |
特殊限制 |
Subtask 0 (10 pts) |
103 |
1000 ms |
512.00 MB |
|
Subtask 1 (30 pts) |
|
|
A |
Subtask 2 (25 pts) |
B |
Subtask 3 (25 pts) |
3×105 |
400 ms |
|
Subtask 4 (10 pts) |
|
- 限制 A: xn≤2×105。
- 限制 B:有不超过 50 个 i 不满足 xi−xi−1≤100 ,其余 i 满足 ∑ixi−xi−1≤2×105。