如题，写的 $O(tm \log m)$ 被卡到 $44$ 分。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e6+114;
const long long inf = 1e16+114;
long long tr[maxn],tag[maxn];
inline void pushup(int cur){
	tr[cur]=max(tr[cur<<1],tr[cur<<1|1]);
}
inline void pushdown(int cur){
	tr[cur<<1]+=tag[cur];
	tag[cur<<1]+=tag[cur];
	tr[cur<<1|1]+=tag[cur];
	tag[cur<<1|1]+=tag[cur];
	tag[cur]=0;
}
void update(int cur,int lt,int rt,int l,int r,long long c){
    if(l>r) return ;
	if(rt<l||r<lt) return ;
	if(l<=lt&&rt<=r){
		tr[cur]+=c;
		tag[cur]+=c;
		return ;
	}
	int mid=(lt+rt)>>1;
	pushdown(cur);
	update(cur<<1,lt,mid,l,r,c);
	update(cur<<1|1,mid+1,rt,l,r,c);
	pushup(cur);
}
unordered_map<int,int> lsh,val;
set<int> vec;//存下所有有意义的天数
struct Node{
	int x,y,v;
}q[maxn];
vector< pair<int,int> > plan[maxn];
int n,m,k,d;
int id,T;
void work(){
	cin>>n>>m>>k>>d;
	for(int i=0;i<maxn;i++) plan[i].clear(),tr[i]=tag[i]=0;
	vec.clear(),lsh.clear(),val.clear();
	vec.insert(n);
	if(n>k) vec.insert(n-k);
	vec.insert(1);
	for(int i=1;i<=m;i++){
		cin>>q[i].x>>q[i].y>>q[i].v;
		vec.insert(q[i].x);
		vec.insert(q[i].x-q[i].y+1);
		if(q[i].x>k) vec.insert(q[i].x-k);
		if(q[i].x+1<=n) vec.insert(q[i].x+1);
		if(q[i].x-q[i].y>=1) vec.insert(q[i].x-q[i].y);
	}
	for(int x:vec) if(lsh[x]==0) lsh[x]=lsh.size(),val[lsh[x]]=x;
    for(int i=1;i<=m;i++) q[i].y=lsh[q[i].x-q[i].y+1],q[i].x=lsh[q[i].x];
    for(int i=1;i<=m;i++) plan[q[i].x].push_back(make_pair(q[i].y,q[i].v));
    long long f=0;//当前天不跑的答案
    int mx=vec.size();
    for(int x:vec){
        long long lstf=f;
        f=max(f,tr[1]);//之前的最大值直接继承过来
        update(1,1,mx,lsh[x-k]+1,lsh[x]-1,-1ll*(x-val[lsh[x]-1])*d);
        update(1,1,mx,lsh[x],lsh[x],lstf-d);
        if(lsh[x-k]!=0) update(1,1,mx,lsh[x-k],lsh[x-k],-inf);
        for(pair<int,int> now:plan[lsh[x]]) update(1,1,mx,lsh[x-k]+1,now.first,now.second);
    }
    cout<<max(f,tr[1])<<'\n';
    return ;
}
int main(){
    //freopen("run.in","r",stdin);
    //freopen("run.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>id>>T;
    while(T--) work();
    return 0;
}