Array Equalizer (Codeforces 1605E)
Tags: Math, two pointers

Jeevan has two arrays $$$a$$$ and $$$b$$$ of size $$$n$$$. He is fond of performing weird operations on arrays. This time, he comes up with two types of operations:  Choose any $$$i$$$ ($$$1 \le i \le n$$$) and increment $$$a_j$$$ by $$$1$$$ for every $$$j$$$ which is a multiple of $$$i$$$ and $$$1 \le j \le n$$$.  Choose any $$$i$$$ ($$$1 \le i \le n$$$) and decrement $$$a_j$$$ by $$$1$$$ for every $$$j$$$ which is a multiple of $$$i$$$ and $$$1 \le j \le n$$$. He wants to convert array $$$a$$$ into an array $$$b$$$ using the minimum total number of operations. However, Jeevan seems to have forgotten the value of $$$b_1$$$. So he makes some guesses. He will ask you $$$q$$$ questions corresponding to his $$$q$$$ guesses, the $$$i$$$-th of which is of the form:   If $$$b_1 = x_i$$$, what is the minimum number of operations required to convert $$$a$$$ to $$$b$$$? Help him by answering each question.

Input: The first line contains a single integer $$$n$$$ $$$(1 \le n \le 2 \cdot 10^{5})$$$  — the size of arrays $$$a$$$ and $$$b$$$.The second line contains $$$n$$$ integers $$$a_1, a_2, ..., a_n$$$ $$$(1 \le a_i \le 10^6)$$$.The third line contains $$$n$$$ integers $$$b_1, b_2, ..., b_n$$$ $$$(1 \le b_i \le 10^6$$$ for $$$i \neq 1$$$; $$$b_1 = -1$$$, representing that the value of $$$b_1$$$ is unknown$$$)$$$.The fourth line contains a single integer $$$q$$$ $$$(1 \le q \le 2 \cdot 10^{5})$$$  — the number of questions.Each of the following $$$q$$$ lines contains a single integer $$$x_i$$$ $$$(1 \le x_i \le 10^6)$$$  — representing the $$$i$$$-th question.

Output: Output $$$q$$$ integers  — the answers to each of his $$$q$$$ questions.

Note: Consider the first test case.  $$$b_1 = 1$$$: We need to convert $$$[3, 7] \rightarrow [1, 5]$$$. We can perform the following operations:$$$[3, 7]$$$ $$$\xrightarrow[\text{decrease}]{\text{i = 1}}$$$ $$$[2, 6]$$$ $$$\xrightarrow[\text{decrease}]{\text{i = 1}}$$$ $$$[1, 5]$$$Hence the answer is $$$2$$$. $$$b_1 = 4$$$: We need to convert $$$[3, 7] \rightarrow [4, 5]$$$. We can perform the following operations: $$$[3, 7]$$$ $$$\xrightarrow[\text{decrease}]{\text{i = 2}}$$$ $$$[3, 6]$$$ $$$\xrightarrow[\text{decrease}]{\text{i = 2}}$$$ $$$[3, 5]$$$ $$$\xrightarrow[\text{increase}]{\text{i = 1}}$$$ $$$[4, 6]$$$ $$$\xrightarrow[\text{decrease}]{\text{i = 2}}$$$ $$$[4, 5]$$$Hence the answer is $$$4$$$. $$$b_1 = 3$$$: We need to convert $$$[3, 7] \rightarrow [3, 5]$$$. We can perform the following operations:$$$[3, 7]$$$ $$$\xrightarrow[\text{decrease}]{\text{i = 2}}$$$ $$$[3, 6]$$$ $$$\xrightarrow[\text{decrease}]{\text{i = 2}}$$$ $$$[3, 5]$$$Hence the answer is $$$2$$$. 

Sample Inputs:
2
3 7
-1 5
3
1
4
3

6
2 5 4 1 3 6
-1 4 6 2 3 5
3
1
8
4

Sample Outputs:
2
4
2

10
29
9

Solution (Python):
import io
import os
import sys
FILE_INPUT_MODE = 0
if FILE_INPUT_MODE >= 0:
    if FILE_INPUT_MODE == 1:
        CURRENT_DIR = os.path.dirname(os.path.abspath(__file__))
        FD = os.open(f'{CURRENT_DIR}\\input.txt', os.O_RDONLY)
    elif FILE_INPUT_MODE == 0:
        FD = 0
    DATA = io.BytesIO(os.read(FD, os.fstat(FD).st_size))
    if FD != 0:
        os.close(FD)

    def input():
        return DATA.readline().decode().rstrip('\r\n')

def main():
    n = int(input())
    a = [int(word) for word in input().strip().split()]
    b = [int(word) for word in input().strip().split()]
    a = [0] + a
    b = [0] + b
    q = int(input())
    query = []
    for i in range(q):
        x = int(input())
        query.append(x)
    s = set(query)
    op = sorted(query)
    b[1] = op[0]
    c = [0 for i in range(n + 1)]
    d = [0 for i in range(n + 1)]
    d[1] = 1
    for i in range(1, n + 1):
        c[i] += a[i] - b[i]
        for j in range(i + i, n + 1, i):
            d[j] -= d[i]
            c[j] -= c[i]
    ans = {}
    pq = []
    x = 0
    for i in range(1, n + 1):
        if c[i] * d[i] <= 0:
            if d[i] != 0:
                x += 1
        else:
            pq.append(abs(c[i]))
    pq.sort(reverse=True)
    ans[op[0]] = sum(map(abs, c))
    z = ans[op[0]]
    for i in range(1, len(op)):
        z += (x - len(pq)) * (op[i] - op[i - 1])
        while len(pq) != 0 and op[i] - op[0] >= pq[-1]:
            y = pq.pop()
            z += (op[i] - op[0] - y) * 2
            x += 1
        ans[op[i]] = z
    sys.stdout.write('\n'.join(map(lambda x: str(ans[x]), query)) + '\n')
if __name__ == '__main__':
    main()

Solution (Python):
import io
import os
import sys
FILE_INPUT_MODE = 0
if FILE_INPUT_MODE >= 0:
    if FILE_INPUT_MODE == 1:
        CURRENT_DIR = os.path.dirname(os.path.abspath(__file__))
        FD = os.open(f'{CURRENT_DIR}\\input.txt', os.O_RDONLY)
    elif FILE_INPUT_MODE == 0:
        FD = 0
    DATA = io.BytesIO(os.read(FD, os.fstat(FD).st_size))
    if FD != 0:
        os.close(FD)

    def input():
        return DATA.readline().decode().rstrip('\r\n')

def main():
    n = int(input())
    a = [int(word) for word in input().strip().split()]
    b = [int(word) for word in input().strip().split()]
    a = [0] + a
    b = [0] + b
    q = int(input())
    query = []
    for i in range(q):
        x = int(input())
        query.append(x)
    s = set(query)
    op = sorted(query)
    b[1] = op[0]
    c = [0 for i in range(n + 1)]
    d = [0 for i in range(n + 1)]
    d[1] = 1
    for i in range(1, n + 1):
        c[i] += a[i] - b[i]
        for j in range(i + i, n + 1, i):
            d[j] -= d[i]
            c[j] -= c[i]
    ans = {}
    pq = []
    x = 0
    for i in range(1, n + 1):
        if c[i] * d[i] <= 0:
            if d[i] != 0:
                x += 1
        else:
            pq.append(abs(c[i]))
    pq.sort(reverse=True)
    ans[op[0]] = sum(map(abs, c))
    z = ans[op[0]]
    for i in range(1, len(op)):
        z += (x - len(pq)) * (op[i] - op[i - 1])
        while len(pq) != 0 and op[i] - op[0] >= pq[-1]:
            y = pq.pop()
            z += (op[i] - op[0] - y) * 2
            x += 1
        ans[op[i]] = z
    for i in range(q):
        print(ans[query[i]])
if __name__ == '__main__':
    main()

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

def prep_array_equalizer(n, a, b):
    corrections = [(a[0], -1)] * n
    for i in range(1, n):
        (u, v) = corrections[i]
        u = a[i] - b[i] - u
        v = -v
        j = i + (i + 1)
        while j < n:
            (u_, v_) = corrections[j]
            corrections[j] = (u + u_, v + v_)
            j += i + 1
        corrections[i] = (u, v)
    irregular = []
    cumm_u = cumm_v = 0
    sum_irr_u = 0
    sum_irr_v = 0
    for (u, v) in corrections:
        if u * v >= 0:
            cumm_u += abs(u)
            cumm_v += abs(v)
        else:
            sum_irr_u -= abs(u)
            sum_irr_v += abs(v)
            irregular += [(u, v)]
    irregular.sort(key=lambda x: abs(x[0]))
    last_u = cumm_u + sum_irr_u
    last_v = cumm_v + sum_irr_v
    max_x = abs(irregular[-1][0])
    uv_by_x = {max_x: (last_u, last_v), 0: (cumm_u - sum_irr_u, cumm_v - sum_irr_v)}
    last_x = max_x
    while len(irregular) > 1:
        (u, v) = irregular.pop()
        last_u += 2 * abs(u)
        last_v -= 2 * abs(v)
        max_x = abs(irregular[-1][0])
        if max_x == last_x:
            continue
        uv_by_x[max_x] = (last_u, last_v)
        last_x = max_x
    return (uv_by_x, sorted(uv_by_x.keys()))

def calc_operations2(uv_by_x, thresholds, x):
    lo = 0
    hi = len(thresholds) - 1
    while hi - lo > 1:
        mid = (lo + hi) // 2
        if thresholds[mid] <= x:
            lo = mid
        else:
            hi = mid
    for k in range(hi, lo - 1, -1):
        if thresholds[k] <= x:
            (u, v) = uv_by_x[thresholds[k]]
            sys.stdout.write(f'{u + v * x}\n')
            return
n = int(input())
a = list(map(int, input().decode().split(' ')))
b = list(map(int, input().decode().split(' ')))
(uv_by_x, thresholds) = prep_array_equalizer(n, a, b)
q = int(input())
for _ in range(q):
    x = int(input())
    calc_operations2(uv_by_x, thresholds, x)