A15329. Tonya and Burenka-179
编程题
普及/提高-
知识点
题目描述
Tonya was given an array of $a$ of length $n$ written on a postcard for his birthday. For some reason, the postcard turned out to be a cyclic array, so the index of the element located strictly to the right of the $n$ -th is $1$ . Tonya wanted to study it better, so he bought a robot "Burenka-179".
A program for Burenka is a pair of numbers $(s, k)$ , where $1 \leq s \leq n$ , $1 \leq k \leq n-1$ . Note that $k$ cannot be equal to $n$ . Initially, Tonya puts the robot in the position of the array $s$ . After that, Burenka makes exactly $n$ steps through the array. If at the beginning of a step Burenka stands in the position $i$ , then the following happens:
1. The number $a_{i}$ is added to the usefulness of the program.
2. "Burenka" moves $k$ positions to the right ( $i := i + k$ is executed, if $i$ becomes greater than $n$ , then $i := i - n$ ).
Help Tonya find the maximum possible usefulness of a program for "Burenka" if the initial usefulness of any program is $0$ .
Also, Tony's friend Ilyusha asks him to change the array $q$ times. Each time he wants to assign $a_p := x$ for a given index $p$ and a value $x$ . You need to find the maximum possible usefulness of the program after each of these changes.
A program for Burenka is a pair of numbers $(s, k)$ , where $1 \leq s \leq n$ , $1 \leq k \leq n-1$ . Note that $k$ cannot be equal to $n$ . Initially, Tonya puts the robot in the position of the array $s$ . After that, Burenka makes exactly $n$ steps through the array. If at the beginning of a step Burenka stands in the position $i$ , then the following happens:
1. The number $a_{i}$ is added to the usefulness of the program.
2. "Burenka" moves $k$ positions to the right ( $i := i + k$ is executed, if $i$ becomes greater than $n$ , then $i := i - n$ ).
Help Tonya find the maximum possible usefulness of a program for "Burenka" if the initial usefulness of any program is $0$ .
Also, Tony's friend Ilyusha asks him to change the array $q$ times. Each time he wants to assign $a_p := x$ for a given index $p$ and a value $x$ . You need to find the maximum possible usefulness of the program after each of these changes.
输入格式
The first line contains a single integer $t$ ( $1 \le t \le 10^4$ ) is the number of test cases. The description of the test cases follows.
The first line of each test case contains two integers $n$ and $q$ ( $2 \le n \le 2 \cdot 10^5$ , $0 \le q \le 2 \cdot 10^5$ ).
The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $1 \le a_i \le 10^9$ ) — elements of the array.
The following $q$ lines contain changes, each of them contains two integers $p$ and $x$ ( $1 \leq p \leq n$ , $1 \leq x \leq 10^9$ ), meaning you should assign $a_p := x$ .
It is guaranteed that the sum of $n$ and the sum of $q$ over all test cases do not exceed $2 \cdot 10^5$ .
The first line of each test case contains two integers $n$ and $q$ ( $2 \le n \le 2 \cdot 10^5$ , $0 \le q \le 2 \cdot 10^5$ ).
The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $1 \le a_i \le 10^9$ ) — elements of the array.
The following $q$ lines contain changes, each of them contains two integers $p$ and $x$ ( $1 \leq p \leq n$ , $1 \leq x \leq 10^9$ ), meaning you should assign $a_p := x$ .
It is guaranteed that the sum of $n$ and the sum of $q$ over all test cases do not exceed $2 \cdot 10^5$ .
输出格式
For each test case, output $q+1$ numbers — the maximum usefulness of a program initially and after each of the changes.
输入输出样例
输入 #1
4 2 1 1 2 1 3 4 4 4 1 3 2 2 6 4 6 1 1 3 11 9 3 1 7 9 4 5 2 3 6 8 3 1 2 1 9 1 6 3 1 1 1 1 1 1 1 5 4 4 3 8
输出 #1
3 5 14 16 24 24 24 57 54 36 36 6 18 27 28
说明/提示
In the first test case, initially and after each request, the answer is achieved at $s = 1$ , $k = 1$ or $s = 2$ , $k = 1$ .
In the second test case, initially, the answer is achieved when $s = 1$ , $k = 2$ or $s = 3$ , $k = 2$ . After the first request, the answer is achieved at $s = 2$ , $k = 2$ or $s = 4$ , $k = 2$ .
In the second test case, initially, the answer is achieved when $s = 1$ , $k = 2$ or $s = 3$ , $k = 2$ . After the first request, the answer is achieved at $s = 2$ , $k = 2$ or $s = 4$ , $k = 2$ .