题解：

首先，我们会发现，在某一天全部买、全部卖一定比分散买卖更优，因为分散买的话我们可以把它们全部集中到最优的一天买卖，答案一定更优。

设f[i]为第i天卖出全部股票最多能得到的钱。

设第i天用f[i]的钱买x的B卷，rate[i]*x的A卷。

则a[i]∗rate[i]∗x+b[i]∗x=f[i]a[i]∗rate[i]∗x+b[i]∗x=f[i]

x∗(a[i]∗rate[i]+b[i])=f[i]x∗(a[i]∗rate[i]+b[i])=f[i]

x=f[i]/(a[i]∗rate[i]+b[i])x=f[i]/(a[i]∗rate[i]+b[i])

所以第i天最多有rate[i]∗f[i]/(a[i]∗rate[i]+b[i])rate[i]∗f[i]/(a[i]∗rate[i]+b[i])的A卷，f[i]/(a[i]∗rate[i]+b[i])f[i]/(a[i]∗rate[i]+b[i])的b卷。

如果第i天再卖出第j天的所有股票，中间不进行任何操作，全部所得利润为

a[i]∗rate[j]∗f[j]/(a[j]∗rate[j]+b[j])+b[i]∗f[j]/(a[j]∗rate[j]+b[j])a[i]∗rate[j]∗f[j]/(a[j]∗rate[j]+b[j])+b[i]∗f[j]/(a[j]∗rate[j]+b[j])

令x[i]=rate[i]∗f[i]/(a[i]∗rate[i]+b[i])x[i]=rate[i]∗f[i]/(a[i]∗rate[i]+b[i]),y[i]=f[i]/(a[i]∗rate[i]+b[i])y[i]=f[i]/(a[i]∗rate[i]+b[i])

原式可以化简为a[i]∗x[j]+b[i]∗y[j]a[i]∗x[j]+b[i]∗y[j]

如果k>j在第i天卖出第k天的所有股票比第i天卖出第j天的所有股票更优且y[j] < y[k]，则有

a[i]∗x[k]+b[i]∗y[k]>=a[i]∗x[j]+b[i]∗y[j]a[i]∗x[k]+b[i]∗y[k]>=a[i]∗x[j]+b[i]∗y[j]

a[i]∗(x[k]−x[j])>=b[i]∗(y[j]−y[k])a[i]∗(x[k]−x[j])>=b[i]∗(y[j]−y[k])

(x[k]−x[j])/(y[j]−y[k])<=b[i]/a[i](x[k]−x[j])/(y[j]−y[k])<=b[i]/a[i]

之后我们可以用cdq分治进行处理。

首先，我们对所有天以b[i]/a[i]b[i]/a[i]递增排序。然后进行分治。

设当前分治到左端点为l，右端点为r的连续的r-l+1天,mid=(l+r)/2。

如果l==r，可以直接先计算f[l]的值。

否则，我们将之前排好序的那个数组一分为二，第mid天及以前的丢左边，剩下的丢右边。两边分别仍然是b[i]/a[i]递增排序的。

接着，分治l~mid的区间。

在下一层分治结束后，我们已经将l~mid按y值递增排序了(这个一会儿再提为什么)，

而且mid~r的b[i]/a[i]值也是递增排序的(这是分治l,mid之前的操作！)。

于是我们就可以直接把l~mid的斜率丢进单调队列里面，然后更新mid+1~r的答案。

(注意，mid+1~r的答案现在并没有确定，只是更新，一会儿分治(mid+1,r)的时候还会被更新到！

随着一次次的分治，你会发现f[i]都被任何j<ij<i的一天更新过答案！)

接着我们分治mid+1~r。

mid+1~r回溯过来之后，我们将l,mid和mid+1~r的y值进行一次归并排序，使得再回溯上一层的l~mid或者mid+1~r的y值是递增排序的。

仔细推敲之后，你会发现这个递归分治过程是那么巧妙，那么精美！

（由于博主语言表达能力有限，请各位看官仔细理解推敲。）

代码：

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;const int N=100005;const double eps=1e-10;int n,q[N];double f[N];struct data{    double a,b,rate,k,x,y;    int id;    friend bool operator < (const data &a,const data &b){        return a.k
        
         0?-1e18:1e18;    }    return (a[k].x-a[j].x)/(a[j].y-a[k].y);}void solve(int l,int r){    if(l==r){        f[l]=max(f[l-1],f[l]);        a[l].y=f[l]/(a[l].a*a[l].rate+a[l].b);        a[l].x=a[l].rate*a[l].y;        return;    }    int mid=(l+r)/2,j=l,k=mid+1;    for(int i=l;i<=r;i++){        if(a[i].id<=mid){            b[j++]=a[i];        }else{            b[k++]=a[i];        }    }    for(int i=l;i<=r;i++){        a[i]=b[i];    }    solve(l,mid);    j=1,k=0;    for(int i=l;i<=mid;i++){        while(j
         
          
           r||a[j].y