前言
打完这道题，感觉对李超线段树又有了进一步的了解。
分析
一个明显的性质，如果要买卷或卖卷的话，那么一定是全买全卖的，显然。
设 \(ans_i\) 为第 \(i\) 天拥有的最大钱数， \(x_i\) 为第 \(i\) 天用 \(ans_i\) 可以兑换的 A 卷数， \(y_j\) 为兑换的 B 卷数。
则有 \(x_i=\dfrac{ans_i\times Rate_i}{Rate_i\times A_i+B_i}\)，\(y_i=\dfrac{ans_i}{Rate_i\times A_i+B_I}\)。
若第 \(i\) 天不卖，那么 \(ans_i=ans_{i-1}\) 。
若第 \(i\) 天卖出卷，那么 \(ans_i=\max\{A_i\times x_j+B_i\times y_j\}\)。
变形得，\(ans_i=B_i\times (\dfrac{A_i}{B_i}\times x_j+y_j)\)。
设 \(k=x_j\)，\(x=\dfrac{A_i}{B_i}\)，\(b=y_j\)，用李超线段树维护即可。
注意到 \(x\) 的值可能为小数，那就不能用李超了吗？我们可以离散化，再映射回去即可。
\(code\)
#include<bits/stdc++.h>
#define N 100005
#define db double
#define ls u<<1
#define rs u<<1|1
#define eps 1e-6
using namespace std;
int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int n;
int tree[N<<2];
db ans;
db A[N],B[N],R[N],C[N],D[N],x[N],y[N];
db calc(int pos,int id){return D[pos]*x[id]+y[id];}
db Query(int u,int l,int r,int X){
if(l==r) return calc(X,tree[u]);
int mid=(l+r)>>1;
db res=calc(X,tree[u]);
if(X<=mid) res=max(res,Query(ls,l,mid,X));
else res=max(res,Query(rs,mid+1,r,X));
return res;
}
void UpDate(int u,int l,int r,int id){
if(calc(l,id)>calc(l,tree[u])&&calc(r,id)>calc(r,tree[u])) return void(tree[u]=id);
else if(calc(l,id)<=calc(l,tree[u])&&calc(r,id)<=calc(r,tree[u])) return ;
int mid=(l+r)>>1;
if(x[id]+eps>x[tree[u]]){
if(calc(mid,id)+eps>calc(mid,tree[u])) UpDate(ls,l,mid,tree[u]),tree[u]=id;
else UpDate(rs,mid+1,r,id);
}else{
if(calc(mid,id)>calc(mid,tree[u])+eps) UpDate(rs,mid+1,r,tree[u]),tree[u]=id;
else UpDate(ls,l,mid,id);
}
}
signed main(){
n=read(),scanf("%lf",&ans);
for(int i=1;i<=n;++i){
scanf("%lf%lf%lf",&A[i],&B[i],&R[i]);
C[i]=D[i]=A[i]/B[i];
}
sort(D+1,D+1+n);
for(int i=1;i<=n;++i){
int X=lower_bound(D+1,D+1+n,C[i])-D;
ans=max(ans,B[i]*Query(1,1,n,X));
x[i]=R[i]*ans/(R[i]*A[i]+B[i]),y[i]=ans/(R[i]*A[i]+B[i]);
UpDate(1,1,n,i);
}
printf("%.3lf\n",ans);
return 0;
}