题解 省选/NOI− DP 线段树优化 DP

题解：[NOIP2023] 天天爱打卡

洛谷P9871

Posted by TH911 on August 5, 2025

题目传送门

记 $[l,r,w]$ 表示 $l\sim r$ 每天都跑步，小 T 请用户吃饭造成的提高为 $w$。

测试点 $1\sim9$

一个非常显然的 $\mathcal O(nk)$ 的 DP。

设 $\textit{dp}_{i,j}$ 为在第 $i$ 天结束时连续打卡了 $j$ 天的最大能量值。

则有：

\[\begin{aligned} \textit{dp}_{i,0}&=\max_{j=0}^{k}\textit{dp}_{i-1,j}\\ \textit{dp}_{i,j}&=\textit{dp}_{i-1,j-1}+\sum_{x_l=i\land j\geq y_l}v_l \end{aligned}\]

答案即 $\max\limits_{i=0}^k\textit{dp}_{n,i}$。

期望得分：$\text{36pts}$。

参考代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
typedef long long ll;
constexpr const int N=1e3,K=N,M=1e5;
vector<pair<int,int> >a[N+1];
int n,m,k,d;
ll dp[N+1][K+1];
void Start(){
	for(int i=1;i<=n;i++){
		a[i].resize(0);
	}
	memset(dp,0,sizeof(dp));
}
int main(){
	/*freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);*/

	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	int c,T;
	cin>>c>>T;
	while(T--){
		Start();
		cin>>n>>m>>k>>d;
		for(int i=1;i<=m;i++){
			int x,y,v;
			cin>>x>>y>>v;
			a[x].push_back({y,v});
		}
		for(int i=1;i<=n;i++){
			dp[i][0]=dp[i-1][0];
			for(int j=1;j<=k;j++){
				dp[i][0]=max(dp[i][0],dp[i-1][j]);
			}
			for(int j=1;j<=k;j++){
				dp[i][j]=dp[i-1][j-1]-d;
				for(auto pl:a[i]){
					int &y=pl.first,&v=pl.second;
					if(j>=y){
						dp[i][j]+=v;
					}
				}
			}
		}
		ll ans=dp[n][0];
		for(int j=1;j<=k;j++){
			ans=max(ans,dp[n][j]);
		}
		cout<<ans<<'\n';
	}
	
	cout.flush();
	 
	/*fclose(stdin);
	fclose(stdout);*/
	return 0;
}

考虑优化上面的 DP，所以更改 DP 状态，因为 $\mathcal O(1)$ 转移已经不能继续优化。

测试点 $1\sim7$

设 \(\textit{dp}_{i,1},\textit{dp}_{i,0}\) 分别为第 $i$ 天是否跑步的最大能量值。

则有：

\(\begin{aligned} \textit{dp}_{i,0}&=\max_{j=1}^{i-1}\textit{dp}_{j,1}=\max\left(\textit{dp}_{i-1,0},\textit{dp}_{i-1,1}\right)\\ \textit{dp}_{i,1}&=\max_{j=1}^{\min(i,k)}\left(\textit{dp}_{i-j,0}-j\cdot d+\operatorname{calc}(i-j+1,i)\right) \end{aligned}\) 其中，$\operatorname{calc}(l,r)$ 表示 $l\sim r$ 一直跑步增加的能量值，显然可以 $\mathcal O(m)$ 计算。

于是得到了一个更劣的 $\mathcal O(nmk)$ 的解法。将给定的 $[l_i,r_i]$ 按照 $r_i$ 排序后单次计算 $\operatorname{calc}(l,r)$ 时在给定区间上二分，可以减小常数。期望复杂度为 $\mathcal O\left(nk\left(\log m+\dfrac mn\right)\right)=\mathcal O\left(nk\log m+mk\right)$。

期望得分 $\text{28pts}$。

参考代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
typedef long long ll;
constexpr const int N=1e5,K=N,M=1e5;
struct line{
	int l,r,w;
}a[M+1];
int n,m,k,d;
ll dp[N+1][2];
ll calc(int l,int r){
	ll ans=0;
	int L=0,R=m;
	while(L<R){
		int mid=L+R+1>>1;
		if(a[mid].r<=r){
			L=mid;
		}else{
			R=mid-1;
		}
	}
	for(int i=L;1<=i&&i<=m&&l<=a[i].r;i--){
		if(l<=a[i].l){
			ans+=a[i].w;
		}
	}
	return ans;
}
void Start(){
	memset(dp,0,sizeof(dp));
}
int main(){
	/*freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);*/

	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	int c,T;
	cin>>c>>T;
	while(T--){
		Start();
		cin>>n>>m>>k>>d;
		for(int i=1;i<=m;i++){
			int &l=a[i].l,&r=a[i].r,&w=a[i].w;
			int x,y;
			cin>>x>>y>>w;
			r=x;
			l=x-y+1;
		}
		sort(a+1,a+m+1,[](line a,line b){
			return a.r<b.r;
		});
//		for(int i=1;i<=m;i++){
//			cerr<<"["<<a[i].l<<","<<a[i].r<<"]:"<<a[i].w<<endl;
//		} 
		for(int i=1;i<=n;i++){
			dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
			dp[i][1]=dp[i-1][0]-d+calc(i,i);
			for(int j=2;j<=i&&j<=k;j++){
				dp[i][1]=max(dp[i][1],dp[i-j][0]-1ll*j*d+calc(i-j+1,i));
			}
		}
		cout<<max(dp[n][0],dp[n][1])<<'\n';
	}
	
	cout.flush();
	 
	/*fclose(stdin);
	fclose(stdout);*/
	return 0;
}

测试点 $8\sim11$

考虑优化上面的 DP。

发现 $\operatorname{calc}(l,r)$ 具有的性质就是 $r$ 单调递增。因此可以想到数据结构维护 $l_i$ 处增加的 $w_i$。

在 DP 之前将 $[l_i,r_i]$ 按 $r_i$ 排序，DP 时依次加入即可。设 $\operatorname{query}(x)$ 表示 $l_i\geq x$ 的 $w_i$ 之和。

则有：

\[\begin{aligned} \textit{dp}_{i,0}&=\max\left(\textit{dp}_{i-1,0},\textit{dp}_{i-1,1}\right)\\ \textit{dp}_{i,1}&=\max_{j=\max(i-k,0)}^{i-1}\left(\textit{dp}_{j,0}-(i-j)d+\operatorname{query}(j+1)\right) \end{aligned}\]

时间复杂度：$\mathcal O((nk+m)\log m)$。期望得分：$\text{36pts}$。原地打转。

参考代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
typedef long long ll;
constexpr const int N=1e5,K=N,M=1e5;
struct BIT{
	ll t[N+1];
	int tag[N+1],Tag;
	void clear(){
		Tag++;
	}
	int lowbit(int x){
		return x&-x;
	}
	ll query(int x){
		ll ans=0;
		while(x<=N){
			if(tag[x]!=Tag){
				t[x]=0;
				tag[x]=Tag;
			}
			ans+=t[x];
			x+=lowbit(x);
		}
		return ans;
	}
	void add(int x,int k){
		while(x){
			if(tag[x]!=Tag){
				t[x]=0;
				tag[x]=Tag;
			}
			t[x]+=k;
			x-=lowbit(x);
		}
	}
}t;
struct line{
	int l,r,w;
}a[M+1];
int n,m,k,d;
ll dp[N+1][2];
void Start(){
	t.clear();
	memset(dp,0,sizeof(dp));
}
int main(){
	/*freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);*/

	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	int c,T;
	cin>>c>>T;
	while(T--){
		Start();
		cin>>n>>m>>k>>d;
		for(int i=1;i<=m;i++){
			int &l=a[i].l,&r=a[i].r,&w=a[i].w;
			int x,y;
			cin>>x>>y>>w;
			r=x;
			l=x-y+1;
		}
		sort(a+1,a+m+1,[](line a,line b){
			if(a.r!=b.r){
				return a.r<b.r;
			}else{
				return a.l<b.l;
			}
		});
		for(int i=1,p=1;i<=n;i++){
			dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
			
			while(p<=m&&a[p].r<=i){
				t.add(a[p].l,a[p].w);
				p++;
			}
			
			dp[i][1]=-1ll<<60;
			for(int j=max(i-k,0);j<i;j++){
				dp[i][1]=max(dp[i][1],dp[j][0] - 1ll*(i-j)*d + t.query(j+1));
			}
		}
		cout<<max(dp[n][0],dp[n][1])<<'\n';
	}
	
	cout.flush();
	 
	/*fclose(stdin);
	fclose(stdout);*/
	return 0;
}

测试点 $10\sim14$

发现 $\textit{dp}_{i,1}$ 的递推式其实是一个区间递推，因此可以考虑线段树优化 DP。

线段树维护 $\textit{dp}{j,0}$ 对于 DP 的贡献，即 $\textit{dp}{j,0}-(i-j)d+\operatorname{query}(j+1)$。

  • $-(i-j)d$ 在 $i$ 变化时可以通过区间加法维护，在 $[0,i-1]$ 上减去 $d$ 即可。
  • $\operatorname{query}(j+1)$ 在 $i$ 变化时维护对应增加的 $[l,r,w]$，在线段树上的 $[0，l-1]$ 这段区间进行区间加法加 $w$ 即可。
  • 查询只需要线段树维护区间 $[\max(i-k,0),i-1]$ 最大值即可。

时间复杂度：$\mathcal O(n\log n+m\log m)$。期望得分：$\text{56pts}$。

参考代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
typedef long long ll;
constexpr const ll inf=0x3f3f3f3f3f3f3f3f;
constexpr const int N=1e5,K=N,M=1e5;
struct line{
	int l,r,w;
}a[M+1];
struct segTree{
	struct node{
		int l,r;
		ll max,tag;
	}t[N<<2|1];

	void up(int p){
		t[p].max=max(t[p<<1].max,t[p<<1|1].max);
	}
	void build(int p,int l,int r){
		t[p].l=l,t[p].r=r;
		t[p].tag=0;
		if(l==r){
			t[p].max=0;
			return;
		}
		int mid=l+r>>1;
		build(p<<1,l,mid);
		build(p<<1|1,mid+1,r);
		up(p);
	}
	void down(int p){
		if(t[p].tag){
			t[p<<1].max+=t[p].tag;
			t[p<<1].tag+=t[p].tag;
			t[p<<1|1].max+=t[p].tag;
			t[p<<1|1].tag+=t[p].tag;
			t[p].tag=0;
		}
	}
	void add(int p,int l,int r,ll k){
		if(l<=t[p].l&&t[p].r<=r){
			t[p].tag+=k;
			t[p].max+=k;
			return;
		}
		down(p);
		if(l<=t[p<<1].r){
			add(p<<1,l,r,k);
		}
		if(t[p<<1|1].l<=r){
			add(p<<1|1,l,r,k);
		}
		up(p);
	}
	ll query(int p,int l,int r){
		if(l<=t[p].l&&t[p].r<=r){
			return t[p].max;
		}
		down(p);
		ll ans=-inf;
		if(l<=t[p<<1].r){
			ans=query(p<<1,l,r);
		}
		if(t[p<<1|1].l<=r){
			ans=max(ans,query(p<<1|1,l,r));
		}
		return ans;
	}
}t;
int n,m,k,d;
ll dp[N+1][2];
int main(){
	/*freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);*/
	
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	int c,T;
	cin>>c>>T;
	while(T--){
		cin>>n>>m>>k>>d;
		t.build(1,0,n);
		for(int i=1;i<=m;i++){
			int &l=a[i].l,&r=a[i].r,&w=a[i].w;
			int x,y;
			cin>>x>>y>>w;
			r=x;
			l=x-y+1;
		}
		sort(a+1,a+m+1,[](line a,line b){
			if(a.r!=b.r){
				return a.r<b.r;
			}else{
				return a.l<b.l;
			}
		});
		for(int i=1,p=1;i<=n;i++){
			dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
			t.add(1,i-1,i-1,dp[i-1][0]);
			while(p<=m&&a[p].r<=i){
				t.add(1,0,a[p].l-1,a[p].w);
				p++;
			}
			t.add(1,0,i-1,-d);
			dp[i][1]=t.query(1,max(i-k,0),i-1);
		}
		cout<<max(dp[n][0],dp[n][1])<<'\n';
	}
	
	cout.flush();
	 
	/*fclose(stdin);
	fclose(stdout);*/
	return 0;
}

测试点 $15\sim25$

考虑优化。

拆式子，得到： \(\textit{dp}_{i,1}=\max_{j=\max(i-k,0)}^{i-1}\left(\textit{dp}_{j,0}+jd+\operatorname{query}(j+1)\right)-id\) 这样，就避免了 $i$ 对 $j$ 的贡献的影响，$j$ 的贡献即 $\textit{dp}_{j,0}+jd+\operatorname{query}(j+1)$。这是确定的，并且可以发现有效的决策点一定是 $l-1$ 和 $r$。那么离散化 $l-1,r$，在 $l-1,r$ 上决策即可。

操作可以在动态开点权值线段树上维护，但是被卡常了。Loj上有 $\text{84pts}$，洛谷上只有 $\text{60pts}$。

参考代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176

//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
namespace io {
	const int SIZE = (1 << 25) + 1;
	char ibuf[SIZE], *iS, *iT;
	char obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[64];
	int f, qr;

	#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
	
	inline void flush () {
		fwrite (obuf, 1, oS - obuf, stdout);
		oS = obuf;
	}
	inline void putc (char x) {
		*oS ++ = x;
		if (oS == oT) flush ();
	}
	template <class I> inline void IN (I &x) {
		for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
		for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); 
		x = f == -1 ? -x : x;
	}
	template <class I> inline void print (I x) {
		if (! x) putc ('0'); if (x < 0) putc ('-'), x = -x;
		while (x) qu[ ++ qr] = x % 10 + '0',  x /= 10;
		while (qr) putc (qu[qr -- ]);
	}
	struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: IN;
using io :: putc;
using io :: print;
typedef long long ll;
constexpr const ll inf=0x3f3f3f3f3f3f3f3f;
constexpr const int N=1e9,K=N,M=1e5;
struct line{
	int l,r,w;
}a[M+1];
struct segTree{
	struct node{
		int l,r;
		ll max,tag;
		int lChild,rChild; 
	}t[M*(__lg(N+1)+1)*3];
	
	int size;
	inline void clear(){
		size=0;
	} 
	inline int create(int l,int r){
		size++;
		t[size]={l,r};
		return size;
	}
	inline void up(int p){
		t[p].max=max(t[t[p].lChild].max,t[t[p].rChild].max);
	}
	inline void down(int p){
		if(!t[p].lChild){
			t[p].lChild=create(t[p].l,t[p].l+t[p].r>>1);
		}
		t[t[p].lChild].max+=t[p].tag;
		t[t[p].lChild].tag+=t[p].tag;
		if(!t[p].rChild){
			t[p].rChild=create((t[p].l+t[p].r>>1)+1,t[p].r);
		}
		t[t[p].rChild].max+=t[p].tag;
		t[t[p].rChild].tag+=t[p].tag;
		t[p].tag=0;
	}
	void add(int p,int l,int r,ll k){
		if(l<=t[p].l&&t[p].r<=r){
			t[p].tag+=k;
			t[p].max+=k;
			return;
		}
		down(p);
		if(l<=t[t[p].lChild].r){
			add(t[p].lChild,l,r,k);
		}
		if(t[t[p].rChild].l<=r){
			add(t[p].rChild,l,r,k);
		}
		up(p);
	}
	ll query(int p,int l,int r){
		if(l<=t[p].l&&t[p].r<=r){
			return t[p].max;
		}
		down(p);
		ll ans=-inf;
		if(l<=t[t[p].lChild].r){
			ans=query(t[p].lChild,l,r);
		}
		if(t[t[p].rChild].l<=r){
			ans=max(ans,query(t[p].rChild,l,r));
		}
		return ans;
	}
}t;
int n,m,k,d;
ll dp[M*3+1][2];
int main(){
	/*freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);*/
	
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	int c,T;
	IN(c);IN(T);
//	cin>>c>>T;
	while(T--){
		IN(n);IN(m);IN(k);IN(d);
//		cin>>n>>m>>k>>d;
		t.clear();
		t.create(0,n);
		static int tmp[M*3+1]; 
		int len=0;
		for(int i=1;i<=m;i++){
			int &l=a[i].l,&r=a[i].r,&w=a[i].w;
			int x,y;
			IN(x);IN(y);IN(w);
//			cin>>x>>y>>w;
			r=x;
			l=x-y+1;
			if(l-1){
				tmp[++len]=l-1;
			}
			tmp[++len]=r;
		}
		sort(tmp+1,tmp+len+1);
		len=unique(tmp+1,tmp+len+1)-tmp-1;
		sort(a+1,a+m+1,[](line a,line b){
			if(a.r!=b.r){
				return a.r<b.r;
			}else{
				return a.l<b.l;
			}
		});
		for(int i=1,p=1;i<=len;i++){
			dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
			t.add(1,tmp[i-1],tmp[i-1],dp[i-1][0] + 1ll*tmp[i-1]*d);
			while(p<=m&&a[p].r<=tmp[i]){
				t.add(1,0,a[p].l-1,a[p].w);
				p++;
			}
			dp[i][1]=t.query(1,max(tmp[i]-k,0),tmp[i]-1)-1ll*tmp[i]*d;
//			cerr<<"dp["<<setw(5)<<i<<"][0]="<<setw(12)<<dp[i][0]<<" "<<"dp["<<setw(5)<<i<<"][1]="<<setw(12)<<dp[i][1]; 
//			cerr<<"  r="<<setw(8)<<a[p-1].r<<endl;
		}
		print(max(dp[len][0],dp[len][1]));
		putc('\n');
//		cout<<max(dp[len][0],dp[len][1])<<'\n';
	}
	
	cout.flush();
	 
	/*fclose(stdin);
	fclose(stdout);*/
	return 0;
}

于是可以写普通线段树维护，时间复杂度 $\mathcal O(m\log m)$。

AC 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140

//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
typedef long long ll; 
constexpr const ll inf=0x3f3f3f3f3f3f3f3f;
constexpr const int N=1e9,K=N,M=1e5;
struct line{
	int l,r,w;
}a[M+1];
struct segTree{
	struct node{
		int l,r;
		ll max,tag;
	}t[M<<4|1];
	
	inline void up(int p){
		t[p].max=max(t[p<<1].max,t[p<<1|1].max);
	}
	void build(int p,int l,int r){
		t[p].l=l,t[p].r=r;
		t[p].tag=0;
		if(l==r){
			t[p].max=0;
			return;
		}
		int mid=l+r>>1;
		build(p<<1,l,mid);
		build(p<<1|1,mid+1,r);
		up(p);
	}
	inline void down(int p){
		if(t[p].tag){
			t[p<<1].max+=t[p].tag;
			t[p<<1].tag+=t[p].tag;
			t[p<<1|1].max+=t[p].tag;
			t[p<<1|1].tag+=t[p].tag;
			t[p].tag=0;
		}
	}
	void add(int p,int l,int r,ll k){
		if(l<=t[p].l&&t[p].r<=r){
			t[p].tag+=k;
			t[p].max+=k;
			return;
		}
		down(p);
		if(l<=t[p<<1].r){
			add(p<<1,l,r,k);
		}
		if(t[p<<1|1].l<=r){
			add(p<<1|1,l,r,k);
		}
		up(p);
	}
	ll query(int p,int l,int r){
		if(l<=t[p].l&&t[p].r<=r){
			return t[p].max;
		}
		down(p);
		ll ans=-inf;
		if(l<=t[p<<1].r){
			ans=query(p<<1,l,r);
		}
		if(t[p<<1|1].l<=r){
			ans=max(ans,query(p<<1|1,l,r));
		}
		return ans;
	}
}t;
int n,m,k,d;
ll dp[M<<1|1][2];
int main(){
	/*freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);*/
	
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	int c,T;
	cin>>c>>T;
	while(T--){
		cin>>n>>m>>k>>d;
		t.build(1,0,m<<1);
		static int tmp[M<<1|1]; 
		int len=0;
		for(int i=1;i<=m;i++){
			int &l=a[i].l,&r=a[i].r,&w=a[i].w;
			int x,y;
			cin>>x>>y>>w;
			r=x;
			l=x-y/*+1*/;
			tmp[++len]=l;
			tmp[++len]=r;
		}
		sort(tmp+1,tmp+len+1);
		len=unique(tmp+1,tmp+len+1)-tmp-1;
		for(int i=1;i<=m;i++){
			a[i].l=lower_bound(tmp+1,tmp+len+1,a[i].l)-tmp;
			a[i].r=lower_bound(tmp+1,tmp+len+1,a[i].r)-tmp;
		}
		sort(a+1,a+m+1,[](line a,line b){
			if(a.r!=b.r){
				return a.r<b.r;
			}else{
				return a.l<b.l;
			}
		});
		for(int i=1,p=1,last=0;i<=len;i++){
			dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
			t.add(1,i-1,i-1,dp[i-1][0] + 1ll*tmp[i-1]*d);
			while(p<=m&&a[p].r<=i){
				t.add(1,0,a[p].l,a[p].w);
				p++;
			}
			while(tmp[last]<tmp[i]-k){
				last++;
			}
			dp[i][1]=t.query(1,last,i-1)-1ll*tmp[i]*d;
		}
		cout<<max(dp[len][0],dp[len][1])<<'\n';
	}
	
	cout.flush();
	 
	/*fclose(stdin);
	fclose(stdout);*/
	return 0;
}
CATALOG
    FEATURED TAGS
    树状数组 题解 提高+/省选− 省选/NOI− DP 普及+/提高 基础算法 数学 组合数学 普及/提高− 贪心 字符串 线段树 未完 图论 平衡树 数论 树形 DP 搜索 Tarjan Trie 二分 位运算 二分答案 状态压缩 FHQ Treap 前端 无聊时候的一点思考 最短路 树链剖分 NOI/NOI+/CTSC
    FRIENDS