Tonya and Burenka-179

题意翻译

### 题目描述 Tonya 收到了一个长度为 $ n $ 的数列，写在了他的生日卡片上。出于某种原因，这个卡片原来是一个循环数组，所以严格位于第 $n$ 个元素右侧的元素的下标是 $ 1 $ 。Tonya 想更好地研究它，所以他买了一个机器人 `Burenka-179`。 Burenka 的程序是一个数对 $ (s, k) $ ，其中 $ 1 \leq s \leq n $ ， $ 1 \leq k \leq n-1 $ 。请注意，$k$ 不能等于 $n$。最初，Tonya 将机器人放在数组 $ s $ 的位置。之后，Burenka 在数组中准确地向前或者向后走了 $ n $ 步。如果在开始的时候，Burenka 站在 $i$ 的位置，那么会发生以下情况： 1. 数字$a_{i}$被加入到了到程序的有用值中。 2. Burenka 向右移动了 $k$ 步（ 一般情况下 $ i := i + k $ ，如果 $ i $ 变得大于 $ n $ ，则 $ i := i - n $ ）。 如果任何程序的初始有用值为 $ 0 $ ，则帮助 Tonya 算出程序最大可能的有用值。 此外，Tonya 的朋友 Ilyusha 要求他更改数组 $ q $ 次。每次他想为给定下标 $ p $ 和值 $ x $ 分配 $ a_p := x $ 。在每次进行这些更改之后，你得再次算出程序的最大可能有用值。 ### 输入格式 第一行包含单个整数 $ t $ ( $ 1 \le t \le 10^4 $ ) 是测试用例的数量。测试用例的描述如下。 每个测试用例的第一行包含两个整数 $ n $ 和 $ q $ ( $ 2 \le n \le 2 \cdot 10^5 $ , $ 0 \le q \le 2 \cdot 10^5 $ )。 每个测试用例的第二行包含 $ n $ 个整数， $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^9 $ ) — 数组的元素。 以下 $ q $ 行每行代表了更改操作，每行包含两个整数 $ p $ 和 $ x $ ( $ 1 \leq p \leq n $ , $ 1 \leq x \leq 10^9 $ )，意味着你应该分配$ a_p := x $ 。 保证所有测试用例的 $ n $ 和 $ q $ 的总和不超过 $ 2 \cdot 10^5 $ 。 ### 输出格式 对于每个测试用例，输出 $ q+1 $ 个数字——程序最初和每次更改后的最大有用值。 ## 提示 在第一个测试用例中，最初时和更改后时，可以在 $ s = 1 $ 、 $ k = 1 $ 或 $ s = 2 $ 、 $ k = 1 $ 处找到答案。 在第二个测试用例中，最初，当 $ s = 1 $ , $ k = 2 $ 或 $ s = 3 $ , $ k = 2 $ 时得到答案。在第一次更改之后，在 $ s = 2 $ , $ k = 2 $ 或 $ s = 4 $ , $ k = 2 $ 处找到答案。

题目描述

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.

输入输出格式

输入格式

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 $ .

输出格式

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 $ .

**题目大意：**

Tonya 收到了一个长度为 $ n $ 的循环数组，他购买了一个机器人 `Burenka-179`，机器人的程序由数对 $ (s, k) $ 定义，其中 $ 1 \leq s \leq n $ 且 $ 1 \leq k \leq n-1 $，且 $ k $ 不能等于 $ n $。机器人从数组位置 $ s $ 开始，在数组中向前或向后移动 $ n $ 步，每步将当前位置的数值累加到程序的有用值中，并向右移动 $ k $ 步。需要计算程序的最大可能有用值。此外，Tonya 的朋友 Ilyusha 会对数组进行 $ q $ 次更改，每次更改后都需要重新计算程序的最大可能有用值。

**输入格式：**

- 第一行包含一个整数 $ t $，表示测试用例的数量。
- 每个测试用例的第一行包含两个整数 $ n $ 和 $ q $。
- 每个测试用例的第二行包含 $ n $ 个整数，表示数组的元素。
- 接下来 $ q $ 行，每行包含两个整数 $ p $ 和 $ x $，表示对数组位置的更改。

**输出格式：**

- 对于每个测试用例，输出 $ q+1 $ 个数字，表示初始以及每次更改后程序的最大有用值。

**输入输出样例：**

**输入样例 #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
```

**说明：**

在第一个测试用例中，最初和每次更改后，最大有用值可以在 $ s = 1 $，$ k = 1 $ 或 $ s = 2 $，$ k = 1 $ 时获得。

在第二个测试用例中，最初，最大有用值可以在 $ s = 1 $，$ k = 2 $ 或 $ s = 3 $，$ k = 2 $ 时获得。第一次更改后，最大有用值可以在 $ s = 2 $，$ k = 2 $ 或 $ s = 4 $，$ k = 2 $ 时获得。**题目大意：** Tonya 收到了一个长度为 $ n $ 的循环数组，他购买了一个机器人 `Burenka-179`，机器人的程序由数对 $ (s, k) $ 定义，其中 $ 1 \leq s \leq n $ 且 $ 1 \leq k \leq n-1 $，且 $ k $ 不能等于 $ n $。机器人从数组位置 $ s $ 开始，在数组中向前或向后移动 $ n $ 步，每步将当前位置的数值累加到程序的有用值中，并向右移动 $ k $ 步。需要计算程序的最大可能有用值。此外，Tonya 的朋友 Ilyusha 会对数组进行 $ q $ 次更改，每次更改后都需要重新计算程序的最大可能有用值。 **输入格式：** - 第一行包含一个整数 $ t $，表示测试用例的数量。 - 每个测试用例的第一行包含两个整数 $ n $ 和 $ q $。 - 每个测试用例的第二行包含 $ n $ 个整数，表示数组的元素。 - 接下来 $ q $ 行，每行包含两个整数 $ p $ 和 $ x $，表示对数组位置的更改。 **输出格式：** - 对于每个测试用例，输出 $ q+1 $ 个数字，表示初始以及每次更改后程序的最大有用值。 **输入输出样例：** **输入样例 #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 ``` **说明：** 在第一个测试用例中，最初和每次更改后，最大有用值可以在 $ s = 1 $，$ k = 1 $ 或 $ s = 2 $，$ k = 1 $ 时获得。 在第二个测试用例中，最初，最大有用值可以在 $ s = 1 $，$ k = 2 $ 或 $ s = 3 $，$ k = 2 $ 时获得。第一次更改后，最大有用值可以在 $ s = 2 $，$ k = 2 $ 或 $ s = 4 $，$ k = 2 $ 时获得。