問題一覧 > 通常問題

No.2169 To Arithmetic

レベル : / AI推定難易度 : 1975 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （解説公開後に AC するまで非表示） / 解いたユーザー数 23
作問者 : first_vil / テスター : 👑 hamamu milkcoffee
お気に入りにしたユーザー ProblemId : 8414 / 自分の提出
問題文最終更新日: 2022-12-18 16:02:18
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2022 (順位表) の他の問題:

Problem Statement

You are given an integer sequence $A=(A_1,A_2,\dots,A_N)$ of length $N$. You may perform the following operation on $A$ any number of times, possibly $0$ times.

  • Choose a pair of integers $(l,r)\ (1 \le l \le r \le N)$, and for each $i\ (l \le i \le r)$, set $A_i:=A_i+1$.

For each $i\ (1 \le i \le Q)$, find the minimum number of operations required to make $A$ an arithmetic sequence with common difference $d_i$.

Input

$N$ $Q$
$A_1$ $A_2$ $\dots$ $A_N$
$d_1$
$d_2$
$\vdots$
$d_Q$
  • All input values are integers.
  • $2 \le N \le 2 \times 10^5$
  • $1 \le Q \le 2 \times 10^5$
  • $1 \le A_i \le 10^9$
  • $|d_i| \le 10^9$

Output

Print $Q$ lines.

On line $i\ (1 \le i \le Q)$, print the minimum number of operations required to make $A$ an arithmetic sequence with common difference $d_i$, followed by a newline.

Sample

Sample 1
Input
4 3
1 4 6 5
2
0
-1
Output
4
6
7

For $d_1=2$, the following sequence of operations minimizes the number of operations.

  • Perform the operation with $(l,r)=(1,1)$ $1$ time. Now, $A=(2,4,6,5)$.
  • Perform the operation with $(l,r)=(4,4)$ $3$ times. Now, $A=(2,4,6,8)$.

For $d_2=0$, the following sequence of operations minimizes the number of operations.

  • Perform the operation with $(l,r)=(1,1)$ $3$ times. Now, $A=(4,4,6,5)$.
  • Perform the operation with $(l,r)=(1,2)$ $2$ times. Now, $A=(6,6,6,5)$.
  • Perform the operation with $(l,r)=(4,4)$ $1$ time. Now, $A=(6,6,6,6)$.

For $d_3=-1$, the following sequence of operations minimizes the number of operations.

  • Perform the operation with $(l,r)=(1,1)$ $4$ times. Now, $A=(5,4,6,5)$.
  • Perform the operation with $(l,r)=(1,2)$ $3$ times. Now, $A=(8,7,6,5)$.
Sample 2
Input
3 2
3 6 9
3
-3
Output
0
12
Sample 3
Input
15 8
5 4 5 19 7 7 6 28 19 6 6 9 12 10 25
-6
6
-19
-28
36
13
19
-10
Output
120
97
286
412
484
174
249
165

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。