不是很难的题.下面讲讲我的思考过程.
首先我看到 \(m\) 很小，类比到之前一道 AT 的题，\(dp_i\) 表示考虑到前 \(i\) 个挑战的最大值，然后推式子，开两颗线段树维护，但是这样似乎无法维护区间的包含关系，即只能做特殊性质 BC.
注：@WrongAnswer_90 说其实是可以过的，但是实现比较麻烦，具体可以看this(/bx/bx)
认为这个假了之后，我就不会了...看了题解后才发现原来可以把状态设计成 \(f_{i,0}\) 表示前 \(i\) 天，第 \(i\) 天不跑的最大收益，\(f_{i,1}\) 表示前 \(i\) 天第 \(i\) 天跑的收益，显然
\[f_{i,0}=\max\limits_{j=1}^i f_{j,1}
\]
\[f_{i,1}=\max\limits_{j=i-k}^{i-1} f_{i,0}-(i-j)\times d+calc(j,i)
\]
其中 \(calc(x, y)\) 表示 \(x + 1\) 到 \(y\) 连续跑能完成的挑战获得的能量值之和。这个可以双指针完成，动态地给 \([0,l_p-1]\) 区间加上 \(v_p\).另外 \(-(i-j) \times d\) 也可以动态，每次区间 \(-d\) 即可。
当前时间复杂度为 \(\mathcal{O}(n \log n)\)，考虑优化，发现决策点（\(i\)，\(j\)）只会为 \(l_i-1\) 和 \(r_i\)，离散化即可，但是上面的动态修改要稍作改动。
时间复杂度 \(\mathcal{O}(m \log m)\)
Code:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, mod = 998244353;
const long long inf = -(1ll << 60);
typedef long long ll;
typedef pair<int, int> pii;
void cmax(ll &x, ll y) { if (x < y) x = y; }
void cmin(int &x, int y) { if (x > y) x = y; }
void add(int &x, int y) { x += y; if (x >= mod) x -= mod; }
void mul(int &x, int y) { x = 1ll * x * y % mod; }
template<typename T>
void dbg(const T &t) { cerr << t << endl; }
template<typename Type, typename... Types>
void dbg(const Type& arg, const Types&... args) {#ifdef ONLINE_JUDGEreturn ;#endifcerr << arg << ' ';dbg(args...);
}
int C, T, n, m, k, d, c[N << 1], tot;
struct Event {int l, r, v;bool operator < (const Event &A) const {return r < A.r;}
} a[N];
struct SegTree {#define ls(x) (x << 1)#define rs(x) ((x << 1) | 1)ll tree[N << 3], tag[N << 3]; //N << 1 << 2 void pushup(int pos) { tree[pos] = max(tree[ls(pos)], tree[rs(pos)]); }void pushdown(int pos) {if (tag[pos]) {ll &t = tag[pos];tree[ls(pos)] += t, tree[rs(pos)] += t;tag[ls(pos)] += t, tag[rs(pos)] += t;t = 0;}}void build(int l = 0, int r = tot - 1, int pos = 1) {tree[pos] = 0ll, tag[pos] = 0ll;if (l == r) {return ;}int mid = (l + r) >> 1;build(l, mid, ls(pos)); build(mid + 1, r, rs(pos));pushup(pos);}void modify(int x, int y, ll v, int l = 0, int r = tot - 1, int pos = 1) {if (x <= l && r <= y) {tree[pos] += v;tag[pos] += v;return ;}pushdown(pos);int mid = (l + r) >> 1;if (x <= mid) modify(x, y, v, l, mid, ls(pos));if (mid < y) modify(x, y, v, mid + 1, r, rs(pos));pushup(pos);}ll query(int x, int y, int l = 0, int r = tot - 1, int pos = 1) {if (x <= l && r <= y) return tree[pos];int mid = (l + r) >> 1;pushdown(pos);ll ans = 0;if (x <= mid) ans = max(ans, query(x, y, l, mid, ls(pos)));if (mid < y) ans = max(ans, query(x, y, mid + 1, r, rs(pos)));return ans; }
} st;
int main() {scanf("%d%d", &C, &T);while (T--) {tot = 0;scanf("%d%d%d%d", &n, &m, &k, &d);for (int i = 1; i <= m; i++) {scanf("%d%d%d", &a[i].r, &a[i].l, &a[i].v);a[i].l = a[i].r - a[i].l + 1 - 1;c[++tot] = a[i].l, c[++tot] = a[i].r;}sort(c + 1, c + tot + 1);tot = unique(c + 1, c + tot + 1) - (c + 1);st.build();for (int i = 1; i <= m; i++) {a[i].l = lower_bound(c + 1, c + tot + 1, a[i].l) - c;a[i].r = lower_bound(c + 1, c + tot + 1, a[i].r) - c;}sort(a + 1, a + m + 1);ll ans = 0;for (int i = 1, j = 1; i <= tot; i++) {st.modify(0, i - 1, -1ll * (c[i] - c[i - 1]) * d);while (j <= m && a[j].r == i) {st.modify(0, a[j].l, a[j].v), j++;}cmax(ans, st.query(lower_bound(c + 1, c + tot + 1, c[i] - k) - c, i - 1));if (i + 1 < tot) st.modify(i + 1, i + 1, ans);} printf("%lld\n", ans);}return 0;
}