传送门
二分答案好题。
题意简述：要求支持动态在一个数列队尾加入一个新的数（保证数列单增），查询所有子数列的 最大值减平均值 的最大值。
然而网上一堆高人是用三分做的。
我们先考虑当前的答案有可能由什么构成。
- 加入最后一个数之前的最大值。
- 加入最后一个数之后，以最后一个数为最大值的值。
于是问题变成了去求min{(∑j=1iai)+ani+1}min\{\frac{(\sum_{j=1}^ia_i)+a_n}{i+1}\}min{i+1(∑j=1iai)+an}
然后令bi=(∑j=1iai)+ani+1，ci=bi−bi−1b_i=\frac{(\sum_{j=1}^ia_i)+a_n}{i+1}，c_i=b_i-b_{i-1}bi=i+1(∑j=1iai)+an，ci=bi−bi−1，可以用作差法证明ccc数组单调，于是二分出ccc最接近0的项就行了。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int N=5e5+5;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
typedef long long ll;
ll sum[N],a[N];
int tot=0;
double Ans=0;
inline void modify(){
int l=1,r=tot-1,ans=1;
while(l<=r){
int mid=l+r>>1;
ll fi=a[tot]-a[mid]*mid+sum[mid-1];
if(fi<=0)r=mid-1;
else l=mid+1,ans=mid;
}
Ans=max(Ans,a[tot]-1.0*(sum[ans]+a[tot])/(ans+1));
}
int main(){
freopen("lx.in","r",stdin);
for(ri op,tt=read();tt;--tt){
op=read();
if(op==1){
a[++tot]=read(),sum[tot]=a[tot]+sum[tot-1];
modify();
}
else printf("%.10lf\n",Ans);
}
return 0;
}