問題一覧 > 通常問題

No.3772 Discrete Addition

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

問題文

長さ $N$ の整数列 $A = (A_1, A_2, \dots, A_N)$ と正整数 $M$ が与えられます．

$Q$ 回のクエリを処理してください． $k$ 回目のクエリでは整数 $i_k, x_k$ が与えられるので， $A_{i_k}$ を $x_k$ に変更した後で，以下の小問題の答えを求めてください．

$A$ に対して，以下の操作を行うことを考えます．操作は $0$ 回以上任意の回数行うことができます．
  • $1 \leq i \leq N$ を満たす整数 $i$ を選び， $A_i$ に $M$ を加算する．
操作後の $A$ に対する $\displaystyle\sum_{i=1}^{N-1} \sum_{j=i+1}^{N} |A_i - A_j|$ として考えられる最小値を求めてください．

入力

$N\ M\ Q$
$A_1\ A_2\ \dots\ A_N$
$i_1\ x_1$
$i_2\ x_2$
$\vdots$
$i_Q\ x_Q$
  • 入力はすべて整数．
  • $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$

出力

$Q$ 行出力してください． $k$ 行目には， $k$ 回目のクエリを処理した時点での小問題の答えを出力してください．

サンプル

サンプル1
入力
3 6 3
0 2 3
3 5
3 4
2 1
出力
6
8
6
  • $1$ つ目のクエリでは， $A = (0,2,5)$ に対して小問題の答えを求めます． $i = 1,2$ に対してそれぞれ操作を $1$ 回ずつ行うことで $A = (6,8,5)$ となり，最小値 $6$ を達成できます．
  • $2$ つ目のクエリでは， $A = (0,2,4)$ に対して小問題の答えを求めます．操作を $1$ 回も行わないことで最小値 $8$ を達成できます．
  • $3$ つ目のクエリでは， $A = (0,1,4)$ に対して小問題の答えを求めます． $i = 1,2$ に対してそれぞれ操作を $1$ 回ずつ行うことで $A = (6,7,4)$ となり，最小値 $6$ を達成できます．
サンプル2
入力
2 4 3
2 2
1 2
2 3
1 1
出力
0
1
2

サンプル3
入力
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
出力
13822085196
13656562848
12563367677
12924158177
13775766675
12912250266
11752731265

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