16pts求调

#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
#define lson rt<<1
#define rson rt<<1|1
#include<cmath>
#define PI acos(-1)
using namespace std;
struct task{
	int l,r;
	long long v;
}a[100005];
int num[200005];
bool cmp(task a,task b){
	return a.r<b.r;
}
struct node{
	ll lazy,mx;
}tr[800005];
void pushup(int rt){
	tr[rt].mx=max(tr[lson].mx,tr[rson].mx);
}void pushdown(int rt){
	if(tr[rt].lazy){
		ll k=tr[rt].lazy;
		tr[rt].lazy=0;
		tr[lson].lazy+=k;
		tr[rson].lazy+=k;
		tr[lson].mx+=k;
		tr[rson].mx+=k;
	}
}void update(int rt,int l,int r,int x,int y,ll k){
	if(l>y||r<x){return ;}
	if(x<=l&&r<=y){
		tr[rt].mx+=k;
		tr[rt].lazy+=k;
		return;
	}int mid=(l+r)>>1;
	pushdown(rt);
	update(lson,l,mid,x,y,k);
	update(rson,mid+1,r,x,y,k); 
	pushup(rt);
}ll query(int rt,int l,int r,int x,int y){
	if(l>y||r<x){return 0;}
	if(x<=l&&r<=y){
		return tr[rt].mx;
	}int mid=(l+r)>>1;
	pushdown(rt);
	return max(query(lson,l,mid,x,y),query(rson,mid+1,r,x,y));
}
int ha(int x){
	return lower_bound(num+1,num+1+num[0],x)-num;
}
int main(){
//	printf("%lf\n",tan(30*PI/180));
	freopen("run2.in","r",stdin);
//	freopen("run.out","w",stdout);
	int c,t;
	scanf("%d%d",&c,&t);
	while(t--){
		num[0]=0;
		int n,m,k,d;
		scanf("%d%d%d%d",&n,&m,&k,&d);
		int c=0;
		for(int i=1; i<=m; i++){
			int x,y;
			ll z;
			scanf("%d%d%lld",&x,&y,&z);
			c++;
			a[c].l=x-y+1;
			num[++num[0]]=a[c].l-1;
			a[c].r=x;
			num[++num[0]]=a[c].r+1;
			a[c].v=z;
		}sort(num+1,num+1+num[0]);
		m=c;
		sort(a+1,a+1+m,cmp);
		num[0]=unique(num+1,num+1+num[0])-num-1;
		for(int i=1; i<=800000; i++)tr[i].lazy=tr[i].mx=0;
		ll ans=0;
		int pos=1;
		for(int i=1; i<=num[0]; i++){
			if(num[i]==0){continue;}
			for(int j=pos; j<=m; j++){
				if(a[j].r>num[i]-1){
					pos=j;
					break;
				}
				update(1,1,num[0],1,ha(a[j].l-1),a[j].v);
			}
			ll g=query(1,1,num[0],ha(num[i]-k-1),ha(num[i]-1))+d;
			update(1,1,num[0],i,i,g);
			ans=max(ans,g-num[i]*1ll*d);
		}printf("%lld\n",ans);
	}
	return 0;
}