图片说明
题意把一个序列操作成字典序最小，每次操作可以把一段l～r区间变成平均数，n<=1000000.
思路：一开始想的是o(N^2)的暴力做法，看到网上提供的类似单调栈+区间长度维护的思想，也就是从前往后遍历，遇到能更新前面区间的数就更新，把平均值放到栈中，然后不断把len更新
代码：

#include<iostream>
#include<cstring>
#include <iomanip> 
using namespace std;
const int N=1000010;
int a[N];
double s[N];
int len[N];
int top;
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
    {
        s[++top]=a[i];
        len[top]=1;
        while(top>1 && s[top]<s[top-1])
        {
            s[top-1]=(1.0*s[top]*len[top]+s[top-1]*len[top-1])/(len[top-1]+len[top]);
            len[top-1]+=len[top];
            top--;
        }
    }
    for(int i=1;i<=top;i++)
        for(int j=1;j<=len[i];j++)
            printf("%.9lf\n",s[i]);
    return 0;
}