56RE悬关求调

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
int CC,T,n,m,k,d,tree[300002],dp[300002],hsh[300002];
struct chg{int x,y,v;}A[300002];
struct node{int l,r,maxx,addl;}seg[900004];
map<int,int>lsh;
int read()
{
	char ch;int f,x;
	ch=getchar();f=1,x=0;
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar_unlocked();}
	while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar_unlocked();}
	return f*x;
}
void write(int th)
{if(th<0){th*=-1;putchar('-');}if(th<10){putchar(th+'0');return;}
write(th/10);putchar(th%10+'0');return;}
inline bool cmp(chg a,chg b){return a.y<b.y;}
void build_seg(int nod,int l,int r)
{
	seg[nod].l=l,seg[nod].r=r;
	if(l!=r)
		build_seg(nod*2,l,(l+r)/2),
		build_seg(nod*2+1,(l+r)/2+1,r);
}
void pushdown(int nod)
{
	if(seg[nod].l==seg[nod].r)return;
	if(!seg[nod].addl)return;
	seg[nod*2].maxx+=seg[nod].addl;
	seg[nod*2+1].maxx+=seg[nod].addl;
	seg[nod*2].addl+=seg[nod].addl;
	seg[nod*2+1].addl+=seg[nod].addl;
	seg[nod].addl=0;
}
void update(int nod)
{
	if(seg[nod].l==seg[nod].r)return;
	seg[nod].maxx=max(seg[nod*2].maxx,seg[nod*2+1].maxx);
	seg[nod].addl=0;
}
void add(int nod,int l,int r,int c)
{
	if(l>r)return;
	if(l<=seg[nod].l&&seg[nod].r<=r)
	{
		seg[nod].maxx+=c;
		seg[nod].addl+=c;
		return;
	}
	pushdown(nod);
	if(l<=seg[nod*2].r)add(nod*2,l,r,c);
	if(r>=seg[nod*2+1].l)add(nod*2+1,l,r,c);
	update(nod);
}
int ask(int nod,int l,int r)
{
	if(l>r)return 0;
	if(l<=seg[nod].l&&seg[nod].r<=r)return seg[nod].maxx;
	pushdown(nod);
	int ans=-1e18;
	if(l<=seg[nod*2].r)ans=max(ans,ask(nod*2,l,r));
	if(r>=seg[nod*2+1].l)ans=max(ans,ask(nod*2+1,l,r));
	return ans;
}
inline void solve()
{
	lsh.clear();
	n=read(),m=read(),k=read(),d=read();
	for(int i = 1;i <=n*8+1000;i++)seg[i].l=seg[i].r=seg[i].maxx=seg[i].addl=0;
	for(int i = 1;i <=m;i++)
	{
		A[i].x=read(),A[i].y=read(),A[i].v=read(); 
		if(A[i].y>k)i--,m--;
		else if(A[i].x<A[i].y)i--,m--;
		int p=A[i].y;
		A[i].y=A[i].x,A[i].x=A[i].x-p+1;
		lsh[A[i].x]=0;
		lsh[A[i].y]=0;
	}
	build_seg(1,1,lsh.size()+10);
	for(int i = 0;i <=lsh.size()+10;i++)tree[i]=0,dp[i]=0,hsh[i]=0;
	int asdf=1;
	for(map<int,int>::iterator it=lsh.begin();it!=lsh.end();it++,asdf++)
		lsh[(*it).first]=asdf,hsh[asdf]=(*it).first;
	for(int i = 1;i <=m;i++)
		A[i].x=lsh[A[i].x],A[i].y=lsh[A[i].y];
	sort(A+1,A+m+1,cmp);
	int gotten=1;
	int siz=lsh.size();
	for(int i = 1;i <=siz;i++)add(1,i+1,i+1,hsh[i]*d);
	for(int i = 1;i <=siz;i++)
	{
		while(gotten<=m&&A[gotten].y<=i)
			add(1,2,A[gotten].x+1,A[gotten].v),gotten++;
		dp[i]=dp[i-1]+(hsh[i]+1)*d;
		auto left_bound=lower_bound(hsh,hsh+siz+1,hsh[i]-k+1);
		dp[i]=max(dp[i],ask(1,left_bound-hsh+1,i+1));
		dp[i]=dp[i]-(hsh[i]+1)*d;
		if(hsh[i+1]>hsh[i]+1)add(1,i+2,i+2,dp[i]);
		if(hsh[i+2]==hsh[i+1]+1)add(1,i+3,i+3,dp[i]);
	}
	write(dp[lsh.size()]),putchar('\n');
	return;
}
signed main()
{
    CC=read(),T=read();
    while(T--)solve();
    return 0;
}