Codeforces Round #752 Extreme Extension Solution (Java/C++)

Solution:

Obviously, we don't need to consider the operation sequence. Therefore, we directly consider how to perform several operations on a certain number.
It is also obvious that after several operations, we want to split the numbers as evenly as possible.
Take 4 as an example. If we want to split 4 into 2 numbers, we must split into 2 and 2, not 1 and 3. Because if you split it into 1 and 3, on the one hand, it will force the previous number to split into smaller numbers, and on the other hand, it will increase the maximum value.

So we found that for any $a_i$, there are only $\sqrt a_i$ possible ways to split it.
Take $a_i=100$ as an example, suppose $a_{i+1}=40$. We will not split $a_i$ into $[20, 40, 40]$, but into $[33, 33, 34]$.
Take $a_i=100$, $a_{i+1}=3$ as another example. Obviously, we will split it into 32 3s and 2 2s, for a total of 34 numbers. It is not difficult to find that the same method uses 3 as the maximum value, 2 as the minimum value, and splits into 35 numbers, but in fact, we only focus on the smallest split.

So for $a_i$, we maintain the mapping between the maximum value after splitting and the number of operands required for splitting. We maintain it in two parts:

1. Let m denote the number of operations. For $m \leq \sqrt a_i$, $map[\left\lceil \frac{a_i}{m} \right\rceil]=m-1$.
2. For $m>\sqrt a_i$, let k denote the maximum value remaining after several operations. Obviously $m=\left\lceil \frac{a_i}{k} \right\rceil$, and $k< \sqrt a_i$. So there is $map[k]=\left\lceil \frac{a_i}{k} \right\rceil$

Therefore, for each $a_i$, the mapping can be completed in the time of $O(\sqrt a_i)$.
We use $count[a_i][j]$ to indicate how many operations are needed to split $a_i$ so that the maximum value is j. It should be noted here that j is not continuous.

With this mapping, we can give the following dp definition: dp[i][j] represents for all the subarrays ending in $a_i$, when the last bit after splitting is j (that is, when the maximum value is j) , The sum of extreme values. Similarly, it should be noted that j is not continuous.
So there are: $dp[i][j]=count[a_i][j] \cdot i \cdot dp[i-1][k]$, where k is exists in dp[i-1], and is the largest possible value less than or equal to j. At the same time, because there are a total of i subarrays ending in $a_i$, count[a_i][j] needs to be multiplied by i.

The final answer is $\sum dp[i][a_i]$.

Finally, considering both memory cost and time cost, we need to make the following optimizations:

1. Because dp[i] is only related to dp[i-1], it is obvious that state compression can be applied.
2. Although the j in $count[a_i][j]$ and $dp[i][j]$ are not continuous, we find that in the process of calculating count and dp, whether j is in the query or when it is written, It's all in order. Therefore, we can use arrays and indexes instead of Map to complete records and queries. The complexity of using Map is: $O(n\cdot \sqrt a \cdot log(\sqrt a))$, while the complexity of not using Map is: $O(n\cdot \sqrt a)$.

Code:

Java

C++