如题。样例1能过，样例2答案普遍偏小，不知道为什么

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
int c,t;
int n,m,k,d;
int seg_val[200086];
long long sum1[400086],sum2[400086],sum3[400086];
struct seg_point{
    int pos,bel,type;
    bool operator < (const seg_point& rhs)
    {
        return pos<rhs.pos;
    }
}sp[400086];
map<int,int>mp;
struct node{
    int l,r;
    int lpos,rpos;
    long long val;
}tr[1600086];
inline void push_up(int now)
{
    tr[now].val=max(tr[now<<1].val,tr[now<<1|1].val);
}
int mp2[800086];
void build(int now,int l,int r)
{
    tr[now].l=l;
    tr[now].r=r;
    tr[now].val=-0x3f3f3f3f3f3f3f3fll;
    if(l!=r)
    {
        int mid=l+r>>1;
        build(now<<1,l,mid);
        build(now<<1|1,mid+1,r);
        tr[now].lpos=tr[now<<1].lpos;
        tr[now].rpos=tr[now<<1|1].rpos;
    }
    else tr[now].lpos=tr[now].rpos=mp2[l];
}
void update(int now,int pos,long long val)
{
    if(tr[now].l==tr[now].r)
    {
        tr[now].val=val;
        return;
    }
    int mid=tr[now].l+tr[now].r>>1;
    if(pos<=mid)
        update(now<<1,pos,val);
    else update(now<<1|1,pos,val);
    push_up(now);
}
long long query(int now,int l,int r)
{
    if(l<=tr[now].lpos&&tr[now].rpos<=r)
        return tr[now].val;
    long long res=-0x3f3f3f3f3f3f3f3fll;
    if(l<=tr[now<<1].rpos)
        res=max(res,query(now<<1,l,r));
    if(tr[now<<1|1].lpos<=r)
        res=max(res,query(now<<1|1,l,r));
    return res;
}
long long f[400086];
int main()
{
    freopen("run2.in","r",stdin);
    scanf("%d%d",&c,&t);
    while(t--)
    {
        scanf("%d%d%d%d",&n,&m,&k,&d);
        mp.clear();
        for(int i=1;i<=m;i++)
        {
            int x,y;
            scanf("%d%d%d",&x,&y,seg_val+i);
            sp[i*2-1]=(seg_point){x-y+1,i,0};
            sp[i*2]=(seg_point){x,i,1};
            mp[x-y+1]=1;
            mp[x]=1;
        }
        int lsh_tot=1;
        for(map<int,int>::iterator iter=mp.begin();iter!=mp.end();iter++,lsh_tot++)
        {
            iter->second=lsh_tot;
            mp2[lsh_tot]=iter->first;
            map<int,int>::iterator iter2=iter;
            iter2++;
            if(iter2!=mp.end()&&iter2->first!=iter->first+1)
                lsh_tot++,mp2[lsh_tot]=iter->first+1;
        }
        lsh_tot--;
        sort(sp+1,sp+1+2*m);
        for(int i=1,j=1;i<=lsh_tot;i++)
        {
            sum2[i]=sum2[i-1];
            sum3[i]=sum3[i-1];
            while(j<=2*m&&sp[j].pos<=mp2[i])
            {
                if(sp[j].type==0)
                    sum3[i]+=seg_val[sp[j].bel];
                else sum2[i]+=seg_val[sp[j].bel],sum3[i]-=seg_val[sp[j].bel];
                j++;
            }
        }
        sum2[lsh_tot+1]=sum2[lsh_tot];
        sum3[lsh_tot+1]=sum3[lsh_tot];
        build(1,0,lsh_tot);
        long long res=0;
        update(1,0,0);
        for(int i=1;i<=lsh_tot;i++)
        {
            f[i]=query(1,mp2[i]-k-1,max(mp2[i]-2,0))+sum2[i]-1ll*mp2[i]*d;
            update(1,i,f[i]-sum2[i+1]-sum3[i+1]+1ll*(mp2[i]+1)*d);
            res<f[i]?res=f[i]:0;
        }
        printf("%lld\n",res);
    }
    return 0;
}