改编题意：
有n杯水排成一行，第i杯水中有 wi 单位体积的水. 他会选择一个区间 [l,r] ，
并拿一个初始为空的杯子（杯子的容积无限大），他可以重复无限次以下操作：
• 选定任意一杯水i， i∈[l,r] ．
• 使i和它拿着的杯子里的水的体积变为它们的平均值．
小C希望进行若干操作后最大化杯子里的水的体积，设 g(l,r) 为这个最大值．你需要求：

∑l=1n∑r=lng(l,r)n2

精度误差不超过 10−6

Solution:

对于一段区间 [l,r] ，设倒数第i次操作中选的数为 ai .那么最终产生的价值为： ∑r−l+1i=1ai2i
因此我们得到了一个贪心的思路：水量最多的越靠后选，产生的价值越大
考虑如何巧妙的在优秀的复杂度内处理这个问题
贡献法！
考虑第i个位置和一个区间 [l,r] ,这个位置的贡献只与这个区间中比它大的数的个数t有关，因为我们要求的精度误差不超过 10−6 ,所以说如果t过大，这个位置的i就可以视为无贡献,至于t的最大值调调参就好了QWQ
那么我们考虑一个位置i所能产生的贡献 sumi ,
假设左边找到的数的位置从右往左是 l1,l2,...,lT ,右边找到的数的位置从左往右是 r1,r2,...,rT
同时我们定义 l0=r0=1
那么 sumi=wi∗∑Ti=1∑Tj=1(li−1−li)∗(rj−rj−1)∗12u+v−1
=2∗wi∗(∑Ti=1li−1−li2i)∗(∑Tj=1rj−rj−12j)
(此公式并没有处理到上下界时的问题，代码里处理了)
现在我们只需要找出最近的T个大于 wi 的数，把数按照从小到大的顺序计算贡献，用链表维护，每次计算完贡献后吧这个数从链表中删除即可
时间复杂度 O(nT+nlogn)

代码：

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
const int T=50;
struct Q{
    int id,v;
}a[1000010];
int n;
double ans;
int nxt[1000010],pre[1000010];
bool cmp(Q a,Q b)
{
    if (a.v==b.v) return a.id<b.id;
    else return a.v<b.v;
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        scanf("%d",&a[i].v),a[i].id=i;
    sort(a+1,a+1+n,cmp);
    for (int i=1;i<=n;i++) nxt[i]=i+1,pre[i]=i-1;
    for (int i=1;i<=n;i++)
    {
        int x=a[i].id,lp=x,rp=x;
        double l=0,r=0,mi=1;
        for (int j=1;j<=T;j++)
        {
            mi*=0.5;
            if (lp) l+=mi*(lp-pre[lp]),lp=pre[lp];
            if (rp<=n) r+=mi*(nxt[rp]-rp),rp=nxt[rp]; 
        }
        ans+=2*a[i].v*l*r;
        nxt[pre[x]]=nxt[x];pre[nxt[x]]=pre[x];
    }
    printf("%.6f",ans/n/n);
}