RoAlgo Contest #8 | Gya-chan and the gcd operation

Two arrays $A$ and $B$, both with $N$ elements, are given along with the definition of the following function:

long long f(int A[], int B[], int n){
    long long sum = 0;
    for(int i = 1; i <= n; i++)
        for(int j = i+1; j <= n; j++)
            if(B[i] == B[j]) sum += __gcd(A[i], A[j]);
    return sum;
}

Gya-chan, being very eager to open her presents, wakes up in the middle of the night hoping to find them already under the tree. To her surprise, she runs into Santa Claus on her way to the tree. Upset that he was caught, Santa decides to challenge her.

Task

Santa Claus gives Gya-chan $Q$ questions in the form $(a, b)$, and she has to tell the value returned by the function $f$ if $B_a$ is replaced with $b$. Santa's updates are permanent, meaning that after each operation, the changes made to array $B$ will persist.

Input data

The first line contains two numbers, $N$, representing the number of elements in the two arrays, and $Q$, the number of questions. The next two lines contain $N$ numbers each, the first line containing the elements of array $A$, and the second containing the elements of array $B$. The last $Q$ lines contain the questions given by Santa Claus.

Output data

There will be $Q + 1$ lines, the first one designating the initial value of the function, and the next $Q$ lines containing the answers after each modification.

Constraints and clarifications

• $1 \leq N, Q \leq 2 \cdot 10^5$
• $1 \leq A_i \leq 3 \cdot 10^5$, $1 \leq i \leq N$
• $1 \leq B_i \leq N$ after each operation
• Bahoi wants to mess up the problem, but it is completely forbidden!!! The number of distinct elements of array $B$ is $\leq BULAN$. DO NOT You get 5 points if you guess the value of $BULAN$

  #	Points	Constraints
  1	13	$1 \leq N \leq 10$
  2	12	$1 \leq A_i \leq 100$, $1 \leq i \leq N$
  3	19	$1 \leq N \leq 1\ 000$
  4	25	$1 \leq N \leq 10^5$
  5	31	No additional constraints

Example 1

stdin

3 2
2 3 2 
2 2 1 
3 2
2 1

stdout

1
4
2

Explanation

Before the first modification, the value returned by the function $f$ will be $\gcd(2,3) = 1$.
After the first modification, the value returned will be $\gcd(2,2) + \gcd(2,3) + \gcd(2,3) = 2 + 1 + 1 = 4$.

Example 2

stdin

10 4
1 10 9 2 3 10 9 9 1 8 
2 2 2 4 2 1 3 1 1 2 
5 4
4 1
6 3
8 3

stdout

16
11
14
11
19