## Editorial for CCC '23 S2 - Symmetric Mountains

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: AQT

To solve this problem, we will find the asymmetric value for each crop and compute the minimum asymmetric value for each crop's corresponding length. For every subtask, we find different ways to compute the asymmetric value of each crop.

Considering iterating over all crops. A crop is defined by its left endpoint and right endpoint. Hence, we can use a nested for loop to first fix the left endpoint and then fix the right endpoint. There are other ways to loop through crops, such as looping through its left endpoint and its length and vice versa. To find the asymmetric value of a crop, we can have an accumulator and sum up the absolute difference for every such pair by looping over defined in the problem statement. There are such crops, and we need about calculations on average to compute the asymmetric value of each crop; hence, it runs in time that is roughly cubic in the number of mountains.

For this subtask, we note that if we were to find the asymmetric value of each crop, then we have to do it faster than roughly time. Now consider a crop with a left endpoint of and a right endpoint of . We will take a closer look at the formula to compute the asymmetric value:

where . Note that because the array is non-decreasing in this subtask, then it follows that for mountains with indices , we have that . Hence the above formula is equivalent to:

Let , which represents the midpoint of the mountains (it may not be an integer, but that does not matter). Notice that for every term whose index is greater than , it is being added, and for every term whose index is less than it is being subtracted. We can then rearrange the formula to become:

Note that we have simplified this problem into static range sum queries. We can compute them quickly by building a prefix sum array of the mountains' heights (i.e., an array where the th element is the sum of the first elements of ) before iterating through all the crops. Note that to calculate the asymmetric crop, in this case, it will be constant time (i.e., independent of ), so this runs in quadratic time in the number of mountains.