Tonya and Burenka-179 (Codeforces 1718C)
Tags: Greedy, number theory

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:   The number $$$a_{i}$$$ is added to the usefulness of the program.  "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.

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

Output: For each test case, output $$$q+1$$$ numbers — the maximum usefulness of a program initially and after each of the changes.

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

Sample Inputs:
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

Sample Outputs:
3
5
14
16
24
24
24
57
54
36
36
6
18
27
28

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def prime_factorize(n):
    ans = []
    for i in range(2, int(n ** (1 / 2)) + 1):
        while True:
            if n % i:
                break
            ans.append(i)
            n //= i
        if n == 1:
            break
    if not n == 1:
        ans.append(n)
    return ans
t = int(input())
ans = []
pow2 = [1]
for _ in range(25):
    pow2.append(2 * pow2[-1])
for _ in range(t):
    (n, q) = map(int, input().split())
    a = list(map(float, input().split()))
    p = list(set(prime_factorize(n)))
    d = [n // i for i in p]
    d.sort()
    l = len(d)
    (y, z) = ([], [0])
    for u in d:
        z.append(u + z[-1])
        for i in range(u):
            s = 0
            for j in range(i, n, u):
                s += a[j]
            s *= u
            y.append(s)
    m = len(y).bit_length()
    pm = pow2[m]
    ma = [0.0] * (2 * pm)
    for i in range(len(y)):
        ma[i + pm] = y[i]
    for i in range(pm - 1, 0, -1):
        ma[i] = max(ma[2 * i], ma[2 * i + 1])
    ans0 = int(ma[1])
    ans.append(ans0)
    for _ in range(q):
        (p, x) = map(int, input().split())
        p -= 1
        if x == a[p]:
            ans0 = int(ma[1])
            ans.append(ans0)
            continue
        c = x - a[p]
        a[p] = x + 0.0
        for i in range(l):
            j = z[i] + p % d[i]
            y[j] += d[i] * c
            ma[j + pm] = y[j]
            j = (j + pm) // 2
            while j:
                ma[j] = max(ma[2 * j], ma[2 * j + 1])
                j //= 2
        ans0 = int(ma[1])
        ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def prime_factorize(n):
    ans = []
    for i in range(2, int(n ** (1 / 2)) + 1):
        while True:
            if n % i:
                break
            ans.append(i)
            n //= i
        if n == 1:
            break
    if not n == 1:
        ans.append(n)
    return ans
t = int(input())
ans = []
pow2 = [1]
for _ in range(25):
    pow2.append(2 * pow2[-1])
for _ in range(t):
    (n, q) = map(int, input().split())
    a = list(map(int, input().split()))
    p = list(set(prime_factorize(n)))
    d = [n // i for i in p]
    d.sort()
    l = len(d)
    (y, z) = ([], [0])
    for u in d:
        z.append(u + z[-1])
        for i in range(u):
            s = 0
            for j in range(i, n, u):
                s += a[j]
            s *= u
            y.append(s)
    m = len(y).bit_length()
    pm = pow2[m]
    ma = [0] * (2 * pm)
    for i in range(len(y)):
        ma[i + pm] = y[i]
    for i in range(pm - 1, 0, -1):
        ma[i] = max(ma[2 * i], ma[2 * i + 1])
    ans0 = ma[1]
    ans.append(ans0)
    for _ in range(q):
        (p, x) = map(int, input().split())
        p -= 1
        if x == a[p]:
            ans0 = ma[1]
            ans.append(ans0)
            continue
        c = x - a[p]
        a[p] = x
        for i in range(l):
            j = z[i] + p % d[i]
            y[j] += d[i] * c
            ma[j + pm] = y[j]
            j = (j + pm) // 2
            while j and ma[j] ^ max(ma[2 * j], ma[2 * j + 1]):
                ma[j] = max(ma[2 * j], ma[2 * j + 1])
                j //= 2
        ans0 = ma[1]
        ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
class SegmentTree:

    def __init__(self, data, default=0, func=max):
        """"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()
        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, idx):
        return self.data[idx + self._size]

    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1

    def __len__(self):
        return self._len

    def query(self, start, stop):
        """"""
        start += self._size
        stop += self._size
        res_left = res_right = self._default
        while start < stop:
            if start & 1:
                res_left = self._func(res_left, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res_right = self._func(self.data[stop], res_right)
            start >>= 1
            stop >>= 1
        return self._func(res_left, res_right)

    def __repr__(self):
        return 'SegmentTree({0})'.format(self.data)
import sys, random
input = sys.stdin.readline
out = []
t = int(input())
for _ in range(t):
    (n, q) = map(int, input().split())
    a = list(map(int, input().split()))
    pr = []
    m = n
    for i in range(2, 10 ** 3):
        if m % i == 0:
            pr.append(i)
            while m % i == 0:
                m //= i
    if m > 1:
        pr.append(m)
    sz = len(pr)
    ''
    segs = []
    vals = []
    for p in pr:
        m = n // p
        l = [0] * m
        for i in range(n):
            l[i % m] += a[i]
        segs.append(SegmentTree(l))
        vals.append(n // p * segs[-1].data[1])
    out.append(max(vals))
    for _ in range(q):
        (p, x) = map(int, input().split())
        p -= 1
        diff = x - a[p]
        a[p] = x
        for i in range(sz):
            pp = pr[i]
            m = n // pp
            segs[i][p % m] += diff
            vals[i] = n // pp * segs[i].data[1]
        out.append(max(vals))
print('\n'.join(map(str, out)))