Array Equalizer
Contest: Codeforces Round 754 (Div. 2)
Difficulty rating: 2400
Tags: binary search, greedy, implementation, math, number theory, sortings, 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 format:
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 format:
Output $$$q$$$ integers  — the answers to each of his $$$q$$$ questions.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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

Example input:
2
3 7
-1 5
3
1
4
3

Example output:
2
4
2

Example input:
6
2 5 4 1 3 6
-1 4 6 2 3 5
3
1
8
4

Example output:
10
29
9

Editorial:
Firstly let's observe that only the differences $$$b_i - a_i$$$ matter, and not the individual values of $$$a_i$$$ and $$$b_i$$$. So let us create two more arrays $$$A$$$ and $$$B$$$ where initially $$$A_i = 0$$$ and $$$B_i = b_i - a_i$$$ for all $$$i$$$. The problem reduces to making $$$A$$$ equal to $$$B$$$.
Let's have a few definitions for ease of explanation. We define operation "add" $$$k$$$ to $$$i$$$ as: perform the increment operation at $$$i$$$ (and multiples of $$$i$$$), $$$k$$$ times, if $$$k > 0$$$, otherwise perform the decrement operation at $$$i$$$ (and multiples of $$$i$$$), $$$k$$$ times. In both cases, the number of operations performed is $$$|k|$$$.
Let's first solve the problem for only one value of $$$B_1$$$. We notice that problem can be solved using a simple greedy approach. We iterate over the elements from left to right. Let the index of the current element be $$$u$$$.
• Initial arrays: -123456$$$\cdots$$$$$$A$$$$$$0$$$$$$0$$$$$$0$$$$$$0$$$$$$0$$$$$$0$$$$$$\cdots$$$$$$B$$$$$$B_1$$$$$$B_2$$$$$$B_3$$$$$$B_4$$$$$$B_5$$$$$$B_6$$$$$$\cdots$$$add------$$$\cdots$$$
• At $$$u = 1$$$: Applying the operation at $$$i = 1$$$ alone can change the value of $$$A_1$$$. Thereby we "add" $$$B_1$$$ at $$$i = 1$$$ to make $$$A_1 = B_1$$$. The remaining array also gets modified accordingly. Resulting arrays: -123456$$$\cdots$$$$$$A$$$$$$B_1$$$$$$B_1$$$$$$B_1$$$$$$B_1$$$$$$B_1$$$$$$B_1$$$$$$\cdots$$$$$$B$$$$$$B_1$$$$$$B_2$$$$$$B_3$$$$$$B_4$$$$$$B_5$$$$$$B_6$$$$$$\cdots$$$add$$$B_1$$$-----$$$\cdots$$$
• At $$$u = 2$$$: Applying the operation at $$$i = 1$$$ and $$$i = 2$$$ only can change the value of $$$A_2$$$. But since we have already made $$$A_1 = B_1$$$, we will only apply operations at $$$i = 2$$$. We "add" $$$B_2 - B_1$$$ at $$$i = 2$$$. Resulting arrays: -123456$$$\cdots$$$$$$A$$$$$$B_1$$$$$$B_2$$$$$$B_1$$$$$$B_2$$$$$$B_1$$$$$$B_2$$$$$$\cdots$$$$$$B$$$$$$B_1$$$$$$B_2$$$$$$B_3$$$$$$B_4$$$$$$B_5$$$$$$B_6$$$$$$\cdots$$$add$$$B_1$$$$$$B_2 - B_1$$$----$$$\cdots$$$
• At $$$u = 3$$$: Applying the operation at $$$i = 1$$$ and $$$i = 3$$$ only can change the value of $$$A_3$$$. But since we have already made $$$A_1 = B_1$$$, we will only apply operations at $$$i = 3$$$. We "add" $$$B_3 - B_1$$$ at $$$i = 3$$$. Resulting arrays: -123456$$$\cdots$$$$$$A$$$$$$B_1$$$$$$B_2$$$$$$B_3$$$$$$B_2$$$$$$B_1$$$$$$B_3 + B_2 - B_1$$$$$$\cdots$$$$$$B$$$$$$B_1$$$$$$B_2$$$$$$B_3$$$$$$B_4$$$$$$B_5$$$$$$B_6$$$$$$\cdots$$$add$$$B_1$$$$$$B_2 - B_1$$$$$$B_3 - B_1$$$---$$$\cdots$$$
• At $$$u = 4$$$: Applying the operation at $$$i = 1$$$, $$$i = 2$$$ and $$$i = 4$$$ only can change the value of $$$A_4$$$. But since we have already made $$$A_1 = B_1$$$ and $$$A_2$$$ = B_2, we will only apply operations at $$$i = 4$$$. We "add" $$$B_4 - B_2$$$ at $$$i = 4$$$. Resulting arrays: -123456$$$\cdots$$$$$$A$$$$$$B_1$$$$$$B_2$$$$$$B_3$$$$$$B_2$$$$$$B_1$$$$$$B_3 + B_2 - B_1$$$$$$\cdots$$$$$$B$$$$$$B_1$$$$$$B_2$$$$$$B_3$$$$$$B_4$$$$$$B_5$$$$$$B_6$$$$$$\cdots$$$add$$$B_1$$$$$$B_2 - B_1$$$$$$B_3 - B_1$$$$$$B_4 - B_2$$$--$$$\cdots$$$
So we iterate from left to right and at every index $$$u$$$, we "add" $$$(B_u -$$$ current value of $$$A_u)$$$ at $$$i = u$$$. The final answer will be summation of absolute value of these values (i.e. the values written in the "add" row).
However, in the original problem, we have to solve the problem for multiple values of $$$B_1$$$. So let us assume the value of $$$B_1$$$ to be equal to some variable, say $$$x$$$. Let us try to use the same approach with the variable $$$x$$$.
• Initial arrays: -123456$$$\cdots$$$$$$A$$$$$$0$$$$$$0$$$$$$0$$$$$$0$$$$$$0$$$$$$0$$$$$$\cdots$$$$$$B$$$$$$x$$$$$$B_2$$$$$$B_3$$$$$$B_4$$$$$$B_5$$$$$$B_6$$$$$$\cdots$$$add------$$$\cdots$$$
• At $$$u = 1$$$: We "add" $$$x$$$ at $$$i = 1$$$. Resulting arrays: -123456$$$\cdots$$$$$$A$$$$$$x$$$$$$x$$$$$$x$$$$$$x$$$$$$x$$$$$$x$$$$$$\cdots$$$$$$B$$$$$$x$$$$$$B_2$$$$$$B_3$$$$$$B_4$$$$$$B_5$$$$$$B_6$$$$$$\cdots$$$add$$$x$$$-----$$$\cdots$$$
• At $$$u = 2$$$: We "add" $$$B_2 - x$$$ at $$$i = 2$$$. Resulting arrays: -123456$$$\cdots$$$$$$A$$$$$$x$$$$$$B_2$$$$$$x$$$$$$B_2$$$$$$x$$$$$$B_2$$$$$$\cdots$$$$$$B$$$$$$x$$$$$$B_2$$$$$$B_3$$$$$$B_4$$$$$$B_5$$$$$$B_6$$$$$$\cdots$$$add$$$x$$$$$$B_2 - x$$$----$$$\cdots$$$
• At $$$u = 3$$$: We "add" $$$B_3 - x$$$ at $$$i = 3$$$. Resulting arrays: -123456$$$\cdots$$$$$$A$$$$$$x$$$$$$B_2$$$$$$B_3$$$$$$B_2$$$$$$x$$$$$$B_3 + B_2 - x$$$$$$\cdots$$$$$$B$$$$$$x$$$$$$B_2$$$$$$B_3$$$$$$B_4$$$$$$B_5$$$$$$B_6$$$$$$\cdots$$$add$$$x$$$$$$B_2 - x$$$$$$B_3 - x$$$---$$$\cdots$$$
• At $$$u = 4$$$: We "add" $$$B_4 - B_2$$$ at $$$i = 4$$$. Resulting arrays: -123456$$$\cdots$$$$$$A$$$$$$x$$$$$$B_2$$$$$$B_3$$$$$$B_4$$$$$$x$$$$$$B_3 + B_2 - x$$$$$$\cdots$$$$$$B$$$$$$x$$$$$$B_2$$$$$$B_3$$$$$$B_4$$$$$$B_5$$$$$$B_6$$$$$$\cdots$$$add$$$x$$$$$$B_2 - x$$$$$$B_3 - x$$$$$$B_4 - B_2$$$--$$$\cdots$$$
Every cell in the "add" row here will be of the form: $$$c \cdot x + d$$$. The final answer will be the summation of absolute values of these values written in the "add" row.
Also we know,
$$$$$$ |c \cdot x + d| = \begin{cases} c \cdot x + d & x \ge -\frac{d}{c} \\ -(c \cdot x + d) & x \lt -\frac{d}{c} \end{cases} $$$$$$
Note that the above equalities hold only when $$$c \gt 0$$$. So if $$$c$$$ is negative in any term, then we can multiply the entire term with $$$-1$$$ to make it positive since $$$|c \cdot x + d| = |- c \cdot x - d|$$$.
Now, we can store the values of $$$-\frac{d}{c}$$$ for each index in sorted order. And for each query, we can find out, using binary search, which of the absolute value terms will have a positive sign and which of those will have a negative sign. So we can finally calculate the answer using prefix and suffix sums.
Bonus: It turns out that the value of coefficient of $$$x$$$ in the "add" value for the $$$u$$$-th index is $$$c_u = \mu(u)$$$ where $$$\mu$$$ is the mobious function. So $$$-1 \le c_u \le 1$$$.
Time Complexity: $$$\mathcal{O}(n \log n + q \log n)$$$
$$$$$$ \cdots $$$$$$