OCC '19 G2 - A Guessing Game

View as PDF

Submit solution

Points: 25
Time limit: 0.6s
Memory limit: 512M

Problem type

Alex is playing a game with William. Alex gets two sequences: sequence A and sequence W, each of which has N numbers. Alex will show William the sequence W but not the sequence A. The objective of this game is to figure out each number in sequence A.

During the game, William can ask Alex questions as many times as he wants. For each question, William will pick up an interval [L, R] (1 \le L \le R \le N) and ask Alex the sum of a_i for i \in [L, R]. Alex will answer William's question, but will charge William for \gcd(w_L, w_{L+1}, \ldots, w_R) dollars. William wants to use the minimal cost to figure out the sequence A.

Since William is bored, he decides to play this game for Q rounds. Before each round, Alex will re-generate the sequence A. However, Alex is too lazy to re-generate the cost sequence W. So, Alex will only change one number from the previous sequence W. Given the number which Alex will change and the new value, can you help William to find out the minimum cost for figuring out the sequence A in each round of the game?

Input Specification

The first line contains two integers, N and Q, the number of elements in each sequence and the number of rounds William will play.

The second line contains N integers, the initial sequence W.

Q lines of input follow. The i^{th} line contains two integers, p and w_p, which means Alex will pick up the p^{th} element from the previous sequence W and replace it with the new value w_p before the round i.

Output Specification

Print Q lines. The i^{th} line contains one integer, the minimum cost for William to figure out the sequence A in game i.

Sample Input

5 3
1 2 3 4 5
1 2
3 4
5 6

Sample Output


Explanation for Sample Output

The initial sequence W is [1, 2, 3, 4, 5].

Before round 1, Alex will change w_1 to be 2, i.e. the new sequence W is [2, 2, 3, 4, 5].

In round 1, William can ask questions for [1, 5], [1, 4], [2, 5], [1, 3] and [3, 5] with the total cost of 5.

Before round 2, Alex will change w_3 to be 4, i.e. the new sequence W is [2, 2, 4, 4, 5].

In round 2, William can ask questions for [1, 5], [2, 5], [3, 5], [4, 5] and [1, 4] with the total cost of 6.


For all test cases, 1 \le N, Q \le 10^5, 1 \le a_i, w_i \le 10^9, 1 \le L \le R \le N and 1 \le p \le N.

Subtask Points Additional constraints
1 14 N \le 200, Q \le 200
2 21 N \le 10^5, Q = 1
3 23 N \le 10^5, Q \le 1\,000
4 42 No additional constraints.


There are no comments at the moment.