問題一覧 > 通常問題

No.1394 Changing Problems

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 8
作問者 : chineristACchineristAC / テスター : platinumplatinum
0 ProblemId : 5166 / 出題時の順位表
問題文最終更新日: 2021-02-12 20:45:02

問題文

数学教師の chinerist 先生は次の問題をテストで出題しようと考えています。


【問題】

$N$ 個の整数 $A_i\ (1\le i \le N)$ があります。

あなたは以下の操作を好きな回数行えます。

操作: 整数 $k\ (1\le k\le N)$ を選ぶ。そのあと $A_k$ に $N-2$ を足し、それ以外の要素から $1$ を引く

この操作によって $A_i$ の値が負になってもかまいません。

操作を $0$ 回以上行うことですべての $A_i\ (1\le i \le N)$ が $N-2$ 以下になるようにしたいです。これは有限回の操作で達成できることが証明できます。

必要な操作の最小回数を求めてください。


はじめに与える $N,\ A_i$ は、過去のテストで出題したときに用意したものがあります。

しかし、そのまま出すのはまずいので $A_i$ の値をいろいろ変えてみることにしました。


chinerist 先生が用意していた整数 $N$ と $N$ 個の整数 $A_i\ (1\le i \le N)$ が与えられます。

$Q$ 個のクエリが与えられるのですべて処理してください。

各クエリでは $2$ つの整数 $i,\ x\ (1\ \le i \le N)$ が与えられるので $A_i$ を $x$ に変更し、変更後の $A_i\ (1\le i \le N)$ に対する上の問題の答えを出力してください。

入力

$N$
$A_1\ A_2\ \dots\ A_N$
$Q$
$i_1\ x_1$
$\vdots$
$i_Q\ x_Q$

  • $1\le N\le 2\times 10^5$
  • $0\le A_i\le 10^9\ (1\le i\le N)$
  • $1\le Q\le 10^5$
  • $1\le i_q\le N\ (1\le q \le Q)$
  • $0\le x_q\le 10^9\ (1\le q\ \le Q)$
  • 与えられる入力はすべて整数

出力

$Q$ 行出力してください。

$q$ 行目には $q$ 番目のクエリでの問題の答えを出力してください。

最後に改行してください。

サンプル

サンプル1
入力
3
1 2 3
1
1 1
出力
4

$A_i\ (1\le i \le N)$ が $1,\ 2,\ 3$ のときの問題に対する答えを考えます。

例えば以下のように操作をすると $4$ 回で条件を達成できます。

  • $k=1$ とする。 $A_i\ (1\le i\le N)$ は $2,\ 1,\ 2$ に変わる
  • $k=3$ とする。 $A_i\ (1\le i\le N)$ は $1,\ 0,\ 3$ に変わる
  • $k=2$ とする。 $A_i\ (1\le i\le N)$ は $0,\ 1,\ 2$ に変わる
  • $k=1$ とする。 $A_i\ (1\le i\le N)$ は $1,\ 0,\ 1$ に変わる

$3$ 回以内の操作でこの条件は達成できないので答えは $4$ になります。

サンプル2
入力
5
3 3 3 3 3
2
3 3
2 10
出力
0
8

$1$ 行目の出力では $A_i\ (1\le i\le N)$ が $3,\ 3,\ 3,\ 3,\ 3$ のときの問題に対する答えを出力しています。

$2$ 行目の出力では $A_i\ (1\le i\le N)$ が $3,\ 10,\ 3,\ 3,\ 3$ のときの問題に対する答えを出力しています。

サンプル3
入力
15
8 45 47 41 32 31 13 28 46 21 8 8 26 47 15
5
8 41
4 45
1 34
14 25
8 8
出力
303
303
331
317
275

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