题意：
维护一个可重集 \(S\)，支持以下两种操作：
- 插入一个数，保证插入的数不降。
- 找出 \(S\) 的一个子集 \(s\)，使 \(\max(s) - \operatorname{mean}(s)\) 最大，输出这个最大值。其中 \(\max(s)\) 表示 \(s\) 中元素的最大值，\(\operatorname{mean}(s)\) 表示 \(s\) 中元素的平均值。
由于我太菜了，并没有想到贪心，所以我的做法带两个 \(\log\)，最慢点要花 1.5s 才能过。
假设 \(s\) 中的元素从小到大已经排好序，设 \(n=|s|\)，将式子变成分式形式：
\[\begin{aligned} \max(s) - \operatorname{mean}(s)&=s_{n}-\frac{\sum^{n-1}_{i=1}s_i}{n}\\ &=\frac{(n-1)s_{n}-\sum^{n-1}_{i=1}s_i}{n} \end{aligned}\]考虑分数规划，设上式 \(\ge k\)，则有：
\[\begin{aligned} (n-1)s_{n}-\sum^{n-1}_{i=1}s_i&\ge n k\\ (n-1)(s_n-k)-\sum^{n-1}_{i=1}s_i&\ge k \end{aligned}\]先对 \(k\) 二分，不难发现当 \(k\) 确定时，\(s_n\) 越大越好、\(\sum^{n-1}_{i=1}s_i\) 越小越好，因此可以二分 \(n\) 来判断一个 \(k\) 是否合法，时间复杂度 \(O(q\log^2q)\)，这题时限松，能过。
注意实数二分的 eps 不要太小，要不然因为精度问题可能死循环。
代码：
#include<bits/stdc++.h>
#define endl '\n'
#define rep(i, s, e) for(int i = s, i##E = e; i <= i##E; ++i)
#define per(i, s, e) for(int i = s, i##E = e; i >= i##E; --i)
#define F first
#define S second
#define int ll
#define gmin(x, y) ((x > (y)) && (x = (y)))
#define gmax(x, y) ((x < (y)) && (x = (y)))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double f128;
typedef pair<int, int> pii;
constexpr int N = 5e5 + 5;
int q, n, a[N], s[N];
signed main() {
#ifdef ONLINE_JUDGE
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
#endif
cin >> q;
while(q--) {
int op; cin >> op;
if(op == 1) {
int x; cin >> x;
a[++n] = x;
s[n] = s[n - 1] + x;
}
else {
if(n == 1) {
cout << "0\n";
continue;
}
int mx = a[n];
double l = 0, r = 1e10;
while(r - l > 1e-6) {
double mid = (l + r) / 2;
int p = lower_bound(a + 1, a + n, mx - mid) - a;
--p;
if(p * mx - p * mid - s[p] >= mid) l = mid;
else r = mid;
}
cout << fixed << setprecision(8) << l << endl;
}
}
return 0;
}