cdq 全WA 求条！（代码有注释）

#include<cstdio>
#include<cmath>
#include<algorithm>

#define y(j) (dp[j]+r[j]*x[j])

using std::min;

const int N=5e5+1;
const double INF=2e18;

long n,m;
long x[N],v[N],ri[N];
int num[N],f[N];//num存储标号，f为归并排序时的辅助数组。
double dp[N],r[N],ans=INF;
int q[N],ql,qr;//单调队列。

void cdq(int l,int _r);

int main()
{
    scanf("%ld %ld",&n,&m);
    for(int i=1;i<=n;++i)
    {
        scanf("%ld %d %ld",x+i,ri+i,v+i);
        r[i]=-1.0/2.0*sqrt(ri[i]);//提前处理决策点的横坐标。
        dp[i]=INF;
        num[i]=i;
    }

    dp[1]=1.0*(v[1]);//初始化。
    cdq(1,n);

    for(int i=1;i<=n;++i)
        if(x[i]+ri[i]>=m)
            ans=min(ans,dp[i]);

    printf("%.3lf",ans);
}

void cdq(int l,int _r)//_r变量名避免与数组r冲突。
{
    if(l==_r) return;

    int mid=(l+_r)>>1;
    cdq(l,mid);//处理左半部分。

    //构造左半部分的下凸包。
    ql=qr=0;
    q[qr]=num[l],++qr;
    for(int i=l+1;i<=mid;++i)
    {
        while(ql+1<qr&&(y(num[i])-y(q[qr-1]))/(r[num[i]]-r[q[qr-1]])<=(y(q[qr-1])-y(q[qr-2]))/(r[q[qr-1]]-r[q[qr-2]])) --qr;
        q[qr]=num[i],++qr;
    }

    //斜率优化
    for(int i=mid+1;i<=_r;++i)
    {
        while(ql+1<qr&&(y(q[ql+1])-y(q[ql]))<=x[i]*(r[q[ql+1]]-r[q[ql]])) ++ql;
        dp[i]=min(dp[i],dp[q[ql]]+r[q[ql]]*(1.0*x[q[ql]]-x[i])+v[i]);
    }

    cdq(mid+1,_r);

    //对标号归并排序。
    int l1=l,l2=mid+1;
    for(int i=l;i<=_r;++i)
        if(l2>_r||r[num[l1]]<r[num[l2]])
        {
            f[i]=num[l1];
            ++l1;
        }
        else
        {
            f[i]=num[l2];
            ++l2;
        }

    for(int i=l;i<=_r;++i)
        num[i]=f[i];

    return;
}