来自 这篇笔记 第7部分

（作为唯二AC之一qwq来水题解了）

注：由于AcWing的LaTeX有点奇怪，所以文中所有应该用 {} 表示的minmax全部采用小括号

题目链接
luogu
AcWing

又是 AcWing 众多恶评题之一（

题意

太长了，自己看题

又是用NOI题作结的一天呢

本题没有部分分，你的程序的输出只有和标准答案相差不超过 $0.0010.001$ 时，才能获得该测试点的满分，否则不得分。

输入文件可能很大，请采用快速的读入方式。

必然存在一种最优的买卖方案满足：

每次买进操作使用完所有的人民币，每次卖出操作卖出所有的金券。

思路

这道题就是典型的不能单调栈，要平衡树或者 CDQ 的题目 就算是早年NOI也没那么简单呢qaq

设 $f[i]$ 表示到第 $i$ 天最多有多少钱，$g[i]$ 表示用第 $i$ 天的钱最多能买多少 $B$ 券。易知 $g[i]=\dfrac{f[i]}{r[i]\times a[i]+b[i]}$

得到转移：
$$ f[i]=max( max_{j=1}^{i-1}( g[j]\times \dfrac{b[i]}{a[i]}+r[j]\times g[j] ) \times a[i],f[i-1]) $$
外面的 $max$ 单独判断即可。主要是斜优里面那个式子。
$$ x=\dfrac{b[i]}{a[i]},k=g[j],b=r[j]\times g[j] $$
但是你发现斜率不单调。所以根据前文所述，要使用平衡树或者CDQ分治维护了。

由于平衡树 太长 太板子了，这里就不作介绍，采用 CDQ分治维护。

CDQ分治比较好的总结可以看这里，顺便我的LCT也是这个博主教的

现在 假装你已经会CDQ分治了 考虑分治，对于任意一个 $f[i]$ ，只需要考虑 $1\leq j\leq i-1$ 即可，和CDQ的解决方式非常相像。

对于一段区间 $[l,r]$ ，先递归左子区间 $[l,m]$ 保证 $[l,m]$ 的 $f,g$ 都已经得到；把左子区间按 $k$ 递增排序，就可以按斜率优化 $O(n)$ 转移；再把右子区间按在原序列中的位置递增排序，递归。此时左子区间对右子区间的影响已经考虑完毕。注意边界 $l==r$ 。复杂度是 $O(nlog^2n).$

继续优化。考虑 CDQ本身就是类似归并排序的过程，可以用这个去掉排序复杂度。

我们希望得到什么呢？当我们拿到 $[l,r]$ 这个区间的时候，$x$ 是单调的。于是把外面的原序列按 $x$ 递增排序；拿到这个序列之后，我们希望在原序列中靠左的东西去左子区间，把 $[l,r]$ 扫一遍，把在原序列中 $\leq m$ 的东西放左边，$\ge m$ 的东西放右边，而且左右区间对 $x$ 的单调性没有影响。在递归右子区间的时候，希望左子区间回来的时候关于 $k$ 单调递增，所以最后对 $k$ 做一遍归并。复杂度 $O(nlogn).$

代码

写了将近半个晚上啊啊啊啊啊

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const double eps=1e-8;
int q[N],n;
double f[N], g[N];
struct node
{
        int id; double a,b,r,x;
        node() {}
        node( int id,double a,double b,double r ) : id(id),a(a),b(b),r(r),x(b/a) {}
        bool operator < (node tmp ) { return x!=tmp.x ? x<tmp.x : id<tmp.id; }
}p[N],b[N];

double cross( int u,int v ) 
{
        return (p[u].r*g[p[u].id]-p[v].r*g[p[v].id])/(g[p[v].id]-g[p[u].id]);
}

double calc( int u,int v ) { return g[p[u].id]*(p[v].x+p[u].r); }

void update( int u,double v )
{
        if ( f[p[u].id]<v ) f[p[u].id]=v,g[p[u].id]=f[p[u].id]/(p[u].b+p[u].r*p[u].a);
}

void solve( int l,int r )
{
        if ( l==r ) { update(l,f[p[l].id-1]); return; }
        int m=(l+r)>>1,i,h,t;
        for ( h=l,t=m+1,i=l; i<=r; i++ )
                p[i].id<=m ? b[h++]=p[i] : b[t++]=p[i];
        for ( int i=l; i<=r; i++ )
                p[i]=b[i];
        solve( l,m ); h=1; t=0;
        for ( i=l; i<=m; i++ )
        {
                while ( h<t && cross(q[t],i)<cross(q[t-1],i)+eps ) t--;
                q[++t]=i;
        }
        for ( ; i<=r; i++ )
        {
                while ( h<t && calc( q[h],i )<calc( q[h+1],i )+eps ) h++;
                update( i,calc(q[h],i)*p[i].a );
        }
        solve( m+1,r );
        for ( h=l,t=m+1,i=l; h<=m && t<=r; )
                g[p[h].id]<g[p[t].id] ? b[i++]=p[h++] : b[i++]=p[t++];
        while ( h<=m ) b[i++]=p[h++];
        while ( t<=r ) b[i++]=p[t++];
        for ( i=l; i<=r; i++ ) p[i]=b[i];
}

int main()
{
        scanf( "%d%lf",&n,&f[1] );
        double a,b,r;
        for ( int i=1; i<=n; i++ )
                scanf( "%lf%lf%lf",&a,&b,&r ),p[i]=node(i,a,b,r);

        g[1]=f[1]/(p[1].r*p[1].a+p[1].b); sort( p+1,p+1+n );
        solve( 1,n );

        printf( "%.3lf\n",f[n] );
}