上一个帖子的链接

把动态开点线段树改成静态的了，还加了标记永久化。

少离散化了几个点，复杂度从 $\mathcal{O}(m\log n)$ 降至 $\mathcal{O}(m\log m)$，但是目前只能拿到64pts，所以有没有什么卡常高论/kel

#include<bits/stdc++.h>
#define fi first
#define se second
typedef long long ll;
typedef long double ld;
using namespace std;
const ll N=1000010,INF=1e9+7,INFF=0x3f3f3f3f3f3f3f3f;
inline ll max(ll x,ll y){return x>y?x:y;}
inline ll min(ll x,ll y){return x<y?x:y;}
inline void swap(ll &x,ll &y){x^=y^=x^=y;}
ll c,t,n,m,k,d,tot,ans,cnt,s[N];
vector<pair<ll,ll> > h[N];
unordered_map<ll,ll> ls,rs;
inline ll read(){
    char c=getchar();ll x=0,f=1;
    while(c<'0'||'9'<c){if(c=='-')f=-1;c=getchar();}
    while('0'<=c&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
struct SegmentTree{
	ll l,r;
	ll dat,tag;
	#define l(x) tree[x].l
	#define r(x) tree[x].r
	#define dat(x) tree[x].dat
	#define tag(x) tree[x].tag
}tree[N<<2];
void pushup(ll x){
	dat(x)=max(dat(x<<1),dat(x<<1|1))+tag(x);
}
void build(ll x,ll l,ll r){
	l(x)=l;r(x)=r;
	dat(x)=tag(x)=0;
	if(l==r)return;
	ll mid=(l+r)>>1;
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
}
void change(ll x,ll L,ll R,ll val){
	ll l=l(x),r=r(x);
	if(L<=l&&r<=R){
		dat(x)+=val;tag(x)+=val;
		return;
	}
	ll mid=(l+r)>>1;
	if(L<=mid)change(x<<1,L,R,val);
	if(R>mid)change(x<<1|1,L,R,val);
	pushup(x);
}
ll query(ll x,ll L,ll R){
	ll l=l(x),r=r(x);
	if(L<=l&&r<=R)return dat(x);
	ll mid=(l+r)>>1,val=-INFF;
	if(L<=mid)val=max(val,query(x<<1,L,R));
	if(R>mid)val=max(val,query(x<<1|1,L,R));
	return val+tag(x);
}
void add(ll x){
	if(x<=0)return;
	if(!rs[x])s[++tot]=x,rs[x]=tot;
}
int main(){
	c=read();t=read();
	while(t--){
		ans=cnt=tot=0;
		ls.clear();rs.clear();
		n=read();m=read();k=read();d=read();
		for(ll i=1;i<=m;i++){
			ll x=read(),y=read(),v=read();
			if(y<=k){
				ls[x-y+1]=1;
				add(x);add(x-y);
				h[rs[x]].push_back(make_pair(x-y+1,v));
			}
		}
		build(1,0,tot);
		change(1,0,0,-d*n);
		sort(s+1,s+tot+1);
		for(ll i=1;i<=tot;i++){
			ll r=s[i],lst=ans;
			change(1,i,i,-d*(n-r));
			for(pair<ll,ll> z:h[rs[r]]){
				ll ql=lower_bound(s,s+tot+1,z.fi-1)-s;
				change(1,0,ql,z.se);
			}
			ll ql=lower_bound(s,s+tot+1,max(0,r-k))-s;
			ans=max(ans,query(1,ql,i-1)+d*(n-r));
			change(1,i,i,ls[r+1]?lst:ans);
		}
		printf("%lld\n",ans);
		for(ll i=1;i<=tot;i++)h[i].clear();
	}
	return 0;
}