No.2306 [Cherry 5th Tune C] Lying Souls
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
Kazun