谢罪，题目顺序有点问题，这题得放T4。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
【ZSROI R1-C 完美计算】
题目大意：
题目除开第一句话够简洁了。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
20pts:20pts:20pts:
暴力求 i,j,ki,j,ki,j,k，时间复杂度 O(n3)O(n^3)O(n3)。
40pts:40pts:40pts:
暴力求 i,ji,ji,j，注意到分子部分其实是可以弄成前缀和，定义 sis_isi 表示 ∑j=1iaj2\sum_{j=1}^i a_j^2∑j=1i aj2 。答案变为下式
sj−sij2−i2(0≤i<j≤n) \frac{s_j-s_i}{j^2-i^2}(0\le i<j\le n) j2−i2sj −si (0≤i<j≤n)
时间复杂度 O(n2)O(n^2)O(n2)
该子任务的 sis_isi 后面还要用
测试点5:测试点5:测试点5:
maxmaxmax 值为 111，minminmin 值为 12n−1\frac{1}{2n-1}2n−11
100pts:100pts:100pts:
本题有两种满分做法。
* 斜率做法
考虑在平面直角坐标系上建点，若要求出所有点其中两个点组成直线斜率的最小值（可以形象地理解为最为平坦，如图1），可以得出性质：只有在纵坐标相邻的两个点组成直线的斜率才有可能是最小值。 如图2 。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
回归题目，把 (i2,si)(i^2,s_i)(i2,si ) 建点，并将原式子转化为下式
∑k=ijak2j2−(i−1)2=sj−si−1j2−(i−1)2\frac{\sum_{k=i}^j a_k^2}{j^2-(i-1)^2}=\frac{s_j-s_{i-1}}{j^2-(i-1)^2} j2−(i−1)2∑k=ij ak2 =j2−(i−1)2sj −si−1
而点 ((i−1)2,si−1)((i-1)^2,s_{i-1})((i−1)2,si−1 ) 与点 (j2,sj)(j^2,s_j)(j2,sj ) 组成的直线的斜率 kkk 为：
k=y2−y1x2−x1=sj−si−1j2−(i−1)2k=\frac{y_2-y_1}{x_2-x_1}=\frac{s_j-s_{i-1}}{j^2-(i-1)^2} k=x2 −x1 y2 −y1 =j2−(i−1)2sj −si−1
发现原式子就是求点 ((i−1)2,si−1)((i-1)^2,s_{i-1})((i−1)2,si−1 ) 与点 (j2,sj)(j^2,s_j)(j2,sj ) 组成的直线的斜率。因为平方具有非负性，所以 ai2a_i^2ai2 一定非负，所以 sis_isi 一定单调递增，那么求 minminmin 值只需要考虑相邻两点，即求出下式
minai2i2−(i−1)2\min \frac{a_i^2}{i^2-(i-1)^2} mini2−(i−1)2ai2
可以求出。若最小值是 ab\frac{a}{b}ba ，则最大值就是 ba\frac{b}{a}ab ，等价于把横纵坐标倒过来，sis_isi 依旧递增，那相同的方法可做。
时间复杂度：O(n)O(n)O(n)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
* 单调队列+二分
具体的思路和上面有联系，这里不再叙述。
使用一个单调队列，每次队头二分，分别考虑 max,min\max,\minmax,min （参考斜率优化DP），剩下模板。
时间复杂度：O(nlogn)O(nlogn)O(nlogn)
