問題一覧 > 通常問題

No.2306 [Cherry 5th Tune C] Lying Souls

レベル : / AI推定難易度 : 500 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 126
作問者 : 👑 Kazun / テスター : 👑 p-adic
お気に入りにしたユーザー ProblemId : 9019 / 自分の提出
問題文最終更新日: 2023-05-19 14:01:46
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 389 (Until that day when "Cherry Month" is over.) (順位表) の他の問題:

Problem Statement

There are $N$ souls. Each soul has a color, which is represented by an integer between $1$ and $M$, inclusive.

From these $N$ souls, the soul power is defined as follows.

For each $i=1,2, \dots, M$, suppose that $x_i$ of the $N$ souls have color $i$. Then, the soul power is defined as $\displaystyle \sum_{i=1}^M x_i^2$.

Initially, for each $i=1,2, \dots, M$, $A_i$ of the $N$ souls have color $i$.

Now, $Q$ pieces of information have come in, reporting that some of these $N$ souls are lying and have a color different from the one they should really be.

For each $q=1,2, \dots, Q$, the $q$-th piece of information is given as a tuple of $3$ integers $(C_q, K_q, D_q)$, which means the following.

  • Among the souls of color $C_q$, $K_q$ of them are actually of color $D_q$.

Each time a piece of information is given, find the soul power after correcting the colors of the souls based on that information.

Note that the color corrections made by each piece of information carry over to all subsequent ones. Also, the given information may itself contain lies, and there may be souls whose color is corrected multiple times.

Constraints

  • $1 \leq N \leq 10^9$.
  • $2 \leq M \leq 10^5$.
  • $0 \leq A_i \leq N \quad (1 \leq i \leq M)$.
  • $\displaystyle \sum_{i=1}^M A_i=N$.
  • $1 \leq Q \leq 10^5$.
  • $1 \leq C_q \leq M \quad (1 \leq q \leq Q)$.
  • Letting $x_{C_q}$ be the number of souls of color $C_q$ at the time the $q$-th piece of information is given, $1 \leq K_q \leq x_{C_q} \quad (1 \leq q \leq Q)$.
  • $1 \leq D_q \leq M \quad (1 \leq q \leq Q)$.
  • $C_q \neq D_q \quad (1 \leq q \leq Q)$.
  • All inputs are integers.

Input

$N$ $M$
$A_1$ $A_2$ $\cdots$ $A_M$
$Q$
$C_1$ $K_1$ $D_1$
$C_2$ $K_2$ $D_2$
$\vdots$
$C_Q$ $K_Q$ $D_Q$

Output

The output consists of $Q$ lines. On the $q~(1 \leq q \leq Q)$-th line, print as an integer the soul power after the $q$-th piece of information is given and the colors of the souls are corrected.

Do not forget the newline at the end.

Sample

Sample 1
Input
10 3
2 3 5
2
3 2 1
1 4 2
Output
34
58

Initially, there are $10$ souls, and the numbers of souls of color $1$, color $2$, and color $3$ are $2$, $3$, and $5$, respectively.

  • Piece of information number $1$ says "among the souls of color $3$, $2$ of them are of color $1$". Correcting the colors of the souls based on this information gives $x_1=4, x_2=3, x_3=3$, so the soul power is $$x_1^2+x_2^2+x_3^2=4^2+3^2+3^2=34$$ .
  • Piece of information number $2$ says "among the souls of color $1$, $4$ of them are of color $2$". Correcting the colors of the souls based on this information gives $x_1=0, x_2=7, x_3=3$, so the soul power is $$x_1^2+x_2^2+x_3^2=0^2+7^2+3^2=58$$ . Here, among the souls of color $1$, $2$ of them were also corrected by piece of information number $1$.

Sample 2
Input
7777777 7
1111111 1111111 1111111 1111111 1111111 1111111 1111111
1
3 123456 6
Output
8672456348119

The soul power may not fit in a $32$-bit integer.

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