题目描述

给定一个由正整数（最初为空）组成的多重集 S。多重集表示可能存在重复元素的集合。

请你对该集合执行 Q 次操作，操作分为两种：

增加操作，格式为 1 x，将一个正整数 x 加入到集合 S 中。数据保证，x 不小于当前 S 中的任何元素。
询问操作，格式为 2，找到一个当前 S 的子集 s，要求 max(s)−mean(s) 的值应尽可能大，输出 max(s)−mean(s) 的最大可能值。max(s) 表示 s 中最大元素的值，mean(s) 表示 s 中所有元素的平均值。
输入格式
第一行包含整数 Q，表示操作次数。

接下来 Q 行，每行描述一个操作，格式如题面所述。

保证第一个操作一定是增加操作。

输出格式
每个询问操作输出一行结果，一个实数，表示 max(s)−mean(s) 的最大可能值。

输出结果与标准答案之间的绝对或相对误差不超过 10−6 即视为正确。

数据范围
前 5 个测试点满足 1≤Q≤15。
所有测试点满足 1≤Q≤5×105，1≤x≤109。

样例

输入样例1：
6
1 3
2
1 4
2
1 8
2
输出样例1：
0.000000
0.500000
3.000000
输入样例2：
4
1 1
1 4
1 5
2
输出样例2：
2.000000

算法1

max(s)−mean(s) 的最大可能值。

max(s)−mean(s) 的最大可能值，取决于mean(s)最小，最大值（a[n])是确定的;
首先这个序列是非单调递减，也就是后面新加的数不小于前面的数
可以得出一定是从前面获取一段连续的数+最大值（考虑子集的平均值大小分布,如果想不明白，可以去看y总的数学证明）
那么分情况讨论，加进来的数和平均值比较
如果新加进来的数比平均值小，那么这个当前状态的子集元素的平均值一定会减小
如果相等，平均值不变
如果新加进来的数比平均值大，平均值会增加

时间复杂度 小于O(n*m)

参考文献

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+10;
int q,cnt,poi=1;
int n,m,op,x = 1;
double a[N],s[N];
double get(int u)
{
    return a[n] - (s[u-1]+a[n])/u;
}
int main()
{
    cin>>m;
    while (m -- )
    {
        cin>>op;
        if(op==1)
        {
            cin>>a[++n];
            s[n]=s[n-1]+a[n];
        }
        else
        {
            while(x+1<=n&&get(x+1)>get(x))++x;
            printf("%.6lf\n", get(x));
        }
    }
    return 0;
}