CF2029I Variance Challenge

Kevin has recently learned the definition of variance. For an array $ a $ of length $ n $ , the variance of $ a $ is defined as follows: - Let $ x=\dfrac{1}{n}\displaystyle\sum_{i=1}^n a_i $ , i.e., $ x $ is the mean of the array $ a $ ; - Then, the variance of $ a $ is $ $$$ V(a)=\frac{1}{n}\sum_{i=1}^n(a_i-x)^2. $ $

Now, Kevin gives you an array $ a $ consisting of $ n $ integers, as well as an integer $ k $ . You can perform the following operation on $ a $ :

• Select an interval $ \[l,r\] $ ( $ 1\\le l\\le r\\le n $ ), then for each $ l\\le i\\le r $ , increase $ a\_i $ by $ k $ .

For each $ 1\\le p\\le m $ , you have to find the minimum possible variance of $ a $ after exactly $ p $ operations are performed, independently for each $ p $ .

For simplicity, you only need to output the answers multiplied by $ n^2$$$. It can be proven that the results are always integers.

N/A

N/A

In the first test case: - For $ p = 1 $ , you can perform the operation on $ [1, 1] $ , changing $ a $ from $ [1, 2, 2] $ to $ [2, 2, 2] $ . Since all of the elements are equal, the variance is equal to $ 0 $ . - For $ p = 2 $ , you can perform the operation on $ [1, 3] $ and then $ [1, 1] $ , changing $ a $ from $ [1, 2, 2] $ to $ [2, 3, 3] $ to $ [3, 3, 3] $ . Since all of the elements are equal, the variance is equal to $ 0 $ . In the second test case, some possible optimal choices are: - $ p=1 $ : $ [\underline{1,}\,2,2]\to [3,2,2] $ ; - $ p=2 $ : $ [1,\underline{2,2}] \to [\underline{1,}\,4,4] \to [3,4,4] $ . In the third test case, some possible optimal choices are: - $ p=1 $ : $ [10,\underline{1,1,1,1,10,1,1,1,1}]\to[10,2,2,2,2,11,2,2,2,2] $ ; - $ p=2 $ : $ [10,1,1,1,1,10,\underline{1,1,1,1}] \to [10,\underline{1,1,1,1},10,2,2,2,2] \to [10,2,2,2,2,10,2,2,2,2] $ . In the eighth test case, the optimal choice for all $ p $ is to perform the operation on the whole array $ p $ times.