Let’s set k = 1 just for now to make everything more simple. We know that the answer for k = 1 is given by the expression a[1] + max(a[2] — a[1], 0) + max(a[3] — a[2], 0) … + max(a[n] — a[n — 1], 0). The editorial does a good job in explaining this in my opinion. Instead of writing the answer in this form, though, what if we tried to make each a[i] independent of one another? In other words, we want to express the answer as c[1] * a[1] + c[2] * a[2] + … + c[n] * a[n] where each c[i] is some coefficient. Let’s see how we can do this:

Let’s solve it for an array of length 2.

The current expression is a[1] + max(a[2] — a[1], 0)

Let’s define an array coefficients = [0, 0] where coefficients[i] = the coefficient of a[i]

We know that we have a1 isolated in the current expression. So we can set coefficients[1] = 1.

But how do we deal with the max(a[2] — a[1], 0) case?

Let’s assume that a[2] — a[1] > 0. Well then the max(a[2] — a[1], 0) = a[2] — a[1]. So the expression becomes a[1] + a[2] — a[1]. It can be seen that when a[2] — a[1] > 0, we add one to coefficients[2] and we subtract one from coefficients[1]. Our coefficients array will then be [0, 1], and our answer will be c[1] * a[1] + c[2] * a[2], or just a[2].

What happens when a[2] — a[1] < 0? Well then max(a[2] — a[1], 0) = 0 and our expression will just be a[1] + 0. Notice that this does not change our original coefficients array at all so we don’t actually have to change any coefficients. The answer is just a[1].

What about when a[2] — a[1] == 0? Well in this case, we can either not change our coefficients or add one to coefficients[2] and subtract one from coefficients[1]. Since a[2] == a[1], these operations are equivalent.

We can do this for all of the max(a[i + 1] — a[i], 0) values, adding and subtracting from coefficients when necessary.

Code might look something like this:

coefficients = [0] * (len(arr) + 10)
coefficients[0] = 1
 
for i in range(len(arr) - 1):
	if arr[i + 1] > arr[i]:
		coefficients[i + 1] += 1
		coefficients[i] -= 1

And we have solved the problem independently for each a[i] when k = 1.

What about when k != 1? Does it affect our coefficients? k changes our a[i] to ceil(a[i] / k) so it must affect max(a[i + 1] — a[i], 0) and thus coefficients, right?

No. There are two cases

Case 1: changing all a[i] to ceil(a[i] / k) does not change the relative size of all a[i]. In other words, for all i < n, if a[i + 1] > a[i], then ceil(a[i + 1] / k) > ceil(a[i] / k), and if a[i + 1] < a[i], then ceil(a[i + 1] / k) < ceil(a[i] / k). This doesn’t affect the answer because the coefficients are made based on the relative size of each a[i], not the absolute size. Like if a[i + 1] > a[i], then we are adding 1 to c[i + 1] and subtracting 1 from c[i] no matter the size of a[i + 1] and a[i].

Case 2: Changing all a[i] to ceil(a[i] / k) changes the relative size of some a[i]. In other words, for some i, if a[i + 1] > a[i], then ceil(a[i + 1] / k) == ceil(a[i] / k) or if a[i + 1] < a[i] then ceil(a[i + 1] / k) == ceil(a[i] / k) (notice that if a[i + 1] > a[i], we can never have ceil(a[i + 1] / k) < ceil(a[i] / k)). But we see that, in either of these cases, when we originally processed the max(a[i + 1] — a[i], 0), coefficients[i + 1] got the same number of 1 additions as coefficients[i] got 1 subtractions (that is, either coefficients[i + 1] += 1 and coefficients[i] -= 1, or they remained unchanged). Since ceil(a[i + 1] / k) == ceil(a[i] / k), the coefficients do not matter since they “balance” each other out.

So coefficients doesn’t just work for k = 1, it works for all k.

The editorial makes it clear why there are only up to 2sqrt(a[i]) possible ceil(a[i] / k) values for every a[i]. So, using this fact, for each a[i], we can find the ranges of k that make ceil(a[i] / k) equal to the same value. For a specific value x, say L is the lower bound of the k range and R is one above the upper bound. We can just use a difference array called ans and do ans[L] += c[i] * x and ans[R] -= c[i] * x. Let’s say we start at k = 1 and this will be our first L for some x. How can we efficiently find R?

We know that:

ceil(a[i] / L) = x.

Since R > L, we know that ceil(a[i] / R) < x.

ceil(a[i] / R) <= x — 1

So a[i] / R <= x — 1

a[i] / (x — 1) <= R

R = ceil(a[i] / (x — 1))

We can set L = R and then do the same steps for the new L until we have covered all of the ranges. This solution is too slow for python so I had to convert it to c++

from math import ceil
import random
 
def thing(arr):
	if len(arr) == 1:
		ans = []
		for i in range(1, arr[0] + 1):
			ans.append(ceil(arr[0] / i))
		print(*ans)
		return
 
	max_arr = max(arr)
	coefficients = [0] * (len(arr) + 10)
	coefficients[0] = 1
	ans = [0] * (max(arr) + 100)
	ans2 = []
 
	for i in range(len(arr) - 1):
		cur = 0
		if arr[i + 1] > arr[i]:
			coefficients[i + 1] += 1
			coefficients[i] -= 1
 
 
	for i, val in enumerate(arr):
		k = 1
 
		while True:
			x = ceil(val / k)
			if x == 1:
				ans[k] += coefficients[i]
				break
			ans[k] += coefficients[i] * x
			new_k = ceil(val / ceil(x - 1))
			if new_k < len(ans):
				ans[new_k] -= x * coefficients[i]
			k = new_k
 
	pre = 0
	for i in range(1, max(arr) + 1):
		pre += ans[i]
		ans2.append(pre)
 
 
	print(*ans2)
 
input()
thing([int(i) for i in input().split()])

I believe that the editorial does a good job in explaining this one. Here is my implementation anyway (I finally got AC with python).

from math import ceil
 
def thing(arr):
	if len(arr) == 1:
		ans = []
		for i in range(1, arr[0] + 1):
			ans.append(ceil(arr[0] / i))
		print(*ans)
		return
 
	max_arr = max(arr)
	coefficients = [0] * (max_arr + 10)
	ans = [0] * (max_arr + 1)
	
	coefficients[arr[0]] = 1
 
	for i in range(len(arr) - 1):
		if arr[i + 1] > arr[i]:
			coefficients[arr[i + 1]] += 1
			coefficients[arr[i]] -= 1
 
 
	pre2 = []
	pre = 0
 
	for i in coefficients:
		pre += i
		pre2.append(pre)
 
	for k in range(1, max_arr + 1):
		for x in range(1, max_arr // k + 2):
			ans[k] += x * (pre2[min(k * x, max_arr)] - pre2[k * (x - 1)])
 
	print(*ans[1:])
 
input()
thing([int(i) for i in input().split()])