题目大意：根据指定规则生成序列a，在所有长度不小于L的区间中，平均值最大是多少？

1、递推计算序列：根据题目公式计算即可。

2、预处理前缀和：区间平均值，用到区间和，区间和可以通过前缀和O(1)算出来。

3、平均值即斜率：区间i+1到j的平均值是(s[j]-s[i]) / (j-i)，可以使用斜率优化！

平均值最大的区间，必有一个开头和结尾，即用对应的i和j的斜率。

枚举区间右端点，选择最好的左端点：右端点从长度c开始，选择左端点前，把最先的左端点i-c压入单调队列。

如何维护单调队列？

1、相邻3个起点x、y、z，斜率应递增，即xy的斜率应小于yz的斜率。

如果xy斜率大于yz的斜率，那么y永远不可能作为起点：假设右端点斜率增大，z点总优先于y点；假设右端点斜率变小，x点总优先于y点。所以，斜率递减，中间点可以删除。

2、对于斜率单调递增的起点，最终选哪个与终点匹配？斜率最大的！

右端点的斜率与左端点斜率并没有直接关系，当然选斜率最大的起点。从头到尾逐个枚举，斜率的变化是怎样的？因为起点斜率递增，总离不开“先递增后递减”的顺序，当然可以无递增或者无递减。我们可以利用单调性快速找到最优点，甚至可以删除无用的。

对于先递增的序列，只保留最大那个点即可！为什么可以这样做？因为后面的右端点，再也不会选到它：入x的开头，y是第二个点，如果y更好，那么对于后面的右端点，y依然更好，除非后面的右端点比当前的右端点差。

#include <bits/stdc++.h>
#define N 10000005
using namespace std;
long long n, m, c, i, j, k, x, y, z, a[N], s[N], q[N];
double ans;
double xie(int i, int j){
    return 1.0 * (s[i]-s[j]) / (i-j);
}
int main(){
    scanf("%lld%lld", &n, &c);
    scanf("%lld%lld%lld%lld%lld", &a[1], &x, &y, &z, &m);
    s[1] = a[1];
    for(i=2; i<=n; i++){
        a[i] = (x*a[i-1]%m*a[i-1]%m + y*a[i-2] + z) % m + m;
        a[i] = a[i] % m - m/2;
        s[i] = s[i-1] + a[i];//预处理序列a、前缀和s
    }
    x = 1, y = 0, ans = xie(c, 0);
    for(i=c; i<=n; i++){
        while(y>x && xie(i-c, q[y]) < xie(q[y], q[y-1])) y--;
        q[++y] = i - c;//起点入队，保持递增，中间无用处
        while(y>x && xie(i, q[x]) < xie(i, q[x+1])) x++;//第2个点更好，虽然不是永远选2，但即使后面选了1，也不比现在好。 
        ans = max(ans, xie(i, q[x]));//选最好的 
    }
    printf("%.8lf\n", ans);
    return 0;
}