問題一覧 > 通常問題

No.3772 Discrete Addition

レベル : / AI推定難易度 : 2900 / 実行時間制限 : 1ケース 8.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 2
作問者 : apricity / テスター : kaichou243
お気に入りにしたユーザー ProblemId : 13529 / 自分の提出
問題文最終更新日: 2026-10-15 21:29:09
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
yukicoder contest 518 (順位表) の他の問題:

Problem Statement

You are given an integer sequence $A = (A_1, A_2, \dots, A_N)$ of length $N$ and a positive integer $M$.

Process $Q$ queries. In the $k$-th query, you are given integers $i_k, x_k$. Change $A_{i_k}$ to $x_k$, and then find the answer to the following subproblem.

Consider performing the following operation on $A$. The operation can be performed any number of times, $0$ or more.
  • Choose an integer $i$ satisfying $1 \leq i \leq N$, and add $M$ to $A_i$.
Find the minimum possible value of $\displaystyle\sum_{i=1}^{N-1} \sum_{j=i+1}^{N} |A_i - A_j|$ for $A$ after the operations.

Input

$N\ M\ Q$
$A_1\ A_2\ \dots\ A_N$
$i_1\ x_1$
$i_2\ x_2$
$\vdots$
$i_Q\ x_Q$
  • All input values are integers.
  • $2 \leq N \leq 10^5$
  • $1 \leq M \leq 10^9$
  • $1 \leq Q \leq 10^5$
  • $0 \leq A_i \leq 10^9$
  • $1 \leq i_k \leq N$
  • $0 \leq x_k \leq 10^9$

Output

Output $Q$ lines. On the $k$-th line, output the answer to the subproblem at the point when the $k$-th query has been processed.

Sample

Sample 1
Input
3 6 3
0 2 3
3 5
3 4
2 1
Output
6
8
6
  • In query number $1$, we find the answer to the subproblem for $A = (0,2,5)$. Performing the operation $1$ time each for $i = 1,2$ gives $A = (6,8,5)$, which achieves the minimum value $6$.
  • In query number $2$, we find the answer to the subproblem for $A = (0,2,4)$. The minimum value $8$ is achieved by not performing the operation even $1$ time.
  • In query number $3$, we find the answer to the subproblem for $A = (0,1,4)$. Performing the operation $1$ time each for $i = 1,2$ gives $A = (6,7,4)$, which achieves the minimum value $6$.
Sample 2
Input
2 4 3
2 2
1 2
2 3
1 1
Output
0
1
2

Sample 3
Input
10 921805637 7
501289994 147590947 116522369 903116546 982632198 973709839 351621724 464019677 716676831 694073257
9 669150000
3 66093366
2 836658913
5 406402938
6 149680516
7 984262145
6 907906816
Output
13822085196
13656562848
12563367677
12924158177
13775766675
12912250266
11752731265

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