← 返回题目列表

Codeforces · 1718/C

C. 托尼亚和布伦卡-179

中文机器翻译题面 查看原题

Tonya 在一张明信片上收到了一个长度为 $$$a$$$ 的数组作为生日礼物。由于某种原因,明信片原来是一个循环数组,因此严格位于第$$$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 找到“Burenka”程序的最大可能有用性。

另外,Tony 的朋友 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$$$ 数字——程序最初和每次更改后的最大有用性。

示例

输入 #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$$$ 处获得答案。