题解

题意：

一共有 $n$ 天，大 Y 可以花费 $d$ 的能量在任何一天跑步，但大 Y 不能在连续的 $k$ 天跑步。

此外，将给出 $m$ 段任务区间 $[l_i,r_i]$。如果在这段区间的每一天都跑了步，则会获得 $v_i$ 的能量。

大 Y 的初始能量为 $0$，请你最大化跑完步后大 Y 最终的能量。

思路：

有一个最朴素的状态设计方案就是 $f_i$ 表示考虑前 $i$ 天并且第 $i$ 天跑步的最大能量值 ，然后定义 $g_i = \max\limits_{j=1}^{i}f_{j}$

转移方程：

$$f_i = \max_{j=i-k + 1}^{\,i} \left\{ g_{j-2} -(i-j + 1)\cdot d + \sum_{[l_p,r_p]\subseteq [j,i]} v_p \right\}$$

这样子直接暴力转移的时间复杂度是$O(nmk)$的。

可以想到，对于枚举的区间 $[j,i]$，能够贡献答案的任务区间 $[l_k,r_k]$ 一定满足$j\le l_k\le r_k\le i$。

现在我们将区间 $[l_i,r_i]$ 看作是二位平面上的点 $(r_i,l_i)$ , 那么我们就能把后面的暴力求和变成求解二维平面上矩形的点权和，于是乎变成了一个基础的二维数点问题。

那么我们按照右端点顺序把任务区间加入，则 $r_k\le i$ 的条件就能天然满足。计算贡献时，我们就只需要查询满足 $l_k\ge j$ 的任务区间的权值和即可，这个可以用树状数组维护，单次计算贡献的复杂度降至 $O(\log m)$，整体时间复杂度$O(nklog_{m})$

接下来考虑优化 $n$ ，由于最终的得分和完成的任务以及跑步的时间有关，因此会发现在一个区间开始或结束的时间开始跑步是一定不劣的，在一个区间的结束的时间完成跑步也一定不劣。因此我们的决策点就只有每个任务的 $l_i , r_i$ 两个点，这样就可以大大的减少状态数量，时间复杂度也就成了 $O(mklog_m)$ ，这就是通过最优性质来保留一定不劣的点，减少状态数。

最后，还剩下一个瓶颈没有解决：对于每一个端点都要枚举前 $k$ 个。所以我们需要接着优化 $dp$ 转移

转移为

$$dp_i = \max_{\substack{1\le j\le i\\ p_i-p_j+1\le k}} \left\{ g_{\mathrm{pre}(j)} +\text{gain}(i,j) -\text{cost}(i,j) \right\}.$$

另外，由于相邻关键天数之间可能存在空档天，需要区分“$p_{j-1}$ 与 $p_j$ 是否相邻”：

$$\mathrm{pre}(j)= \begin{cases} j-2, & j\ge 2\ \text{且}\ p_j=p_{j-1}+1,\\ j-1, & \text{否则}. \end{cases}$$

最后有

$$g_i=\max(g_{i-1},dp_i).$$

接下来我们考虑从 $i \to i+1$的过程中，每个决策点的 $g_{pre(j)}$ 不变，$cost(i,j)$ 变化量一样，$gain(i,j)$ 的变化量取决于 $j$ 的大小，也就是说实际上这是一个区间修改+区间查询的问题，很自然想到用线段树来维护每个决策点 $g_{pre(j)} + gain(i,j) - cost(i,j)$ 的取值，然后在进行区间查询最值即可，查询范围可以双指针快速解决。时间复杂度为$O(mlog_m)$

//
// Created by EDY on 2025/12/19.
//
#include<bits/stdc++.h>
using namespace std;
//二维点对(xi,xi-yi+1)
#define int long long
struct BIT {
    vector<int>f;
    int n;
    BIT(int _n):f(_n),n(_n){}
    int lowbit(int x) {
        return x&(-x);
    }
    void modify(int p, int v) {
        for (int i = p ; i <= n ; i += lowbit(i)) {
            f[i] += v;
        }
    }
    int query(int p) {
        int ans = 0;
        for (int i = p ; i  ; i -= lowbit(i)) {
            ans += f[i];
        }
        return ans;
    }
};
void solve_nmk() {
    int n , m , k , d;
    cin >> n >> m >> k >> d;
    vector <int> dp(n + 5 , 0);
    vector <int> g(n + 5 , 0);
    vector < array<int,3> > v;
    for (int i = 1 ; i <= m ; i ++) {
        array<int,3> tmp;
        cin >> tmp[0] >> tmp[1] >> tmp[2];
        int l = tmp[0] - tmp[1] + 1;
        int r = tmp[0];
        tmp[0] = l;
        tmp[1] = r;
        v.push_back(tmp);
    }
    for (int i = 1 ; i <= n ; i ++) {
        for (int j = max(1LL ,i - k + 1) ; j <= i ; j ++) {
            int del = (i - j + 1) * d;
            int add = 0;
            for (int k = 0 ; k < m ; k ++) {
                if (i >= v[k][1] && j <= v[k][0] && j <= v[k][1]) {
                    add += v[k][2];
                }
            }
            dp[i] = max(dp[i] , g[max(j - 2 , 0LL)] + add - del);
        }
        g[i] = max(g[i - 1] , dp[i]);
    }
    cout << g[n] << endl;
}
void solve_nklogm() {
    int n , m , k , d;
    cin >> n >> m >> k >> d;
    vector <int> dp(n + 5 , 0);
    vector <int> g(n + 5 , 0);
    vector < array<int,3> > v;
    for (int i = 1 ; i <= m ; i ++) {
        array<int,3> tmp;
        cin >> tmp[0] >> tmp[1] >> tmp[2];
        int l = tmp[0] - tmp[1] + 1;
        int r = tmp[0];
        tmp[0] = r;
        tmp[1] = l;
        v.push_back(tmp);
    }
    sort(v.begin() , v.end());
    BIT bit(n + 5);
    int id = 0;
    int sum = 0;
    for (int i = 1 ; i <= n ; i ++) {
        while (id < m && v[id][0] == i) {
            bit.modify(v[id][1] + 1 , v[id][2]);
            sum += v[id][2];
            id++;
        }
        for (int j = max(1LL , i - k + 1) ; j <= i ; j ++) {
            int del = (i - j + 1) * d;
            int add = sum - bit.query(j);
            //cout << i << "  " << j << " " << bit.query(j) << endl;
            dp[i] = max(dp[i] , g[max(j - 2 , 0LL)] + add - del);
        }
        g[i] = max(g[i - 1] , dp[i]);
    }
    cout << g[n] << endl;
}
void solve_mklogm(){
    int n , m , k , d;
    cin >> n >> m >> k >> d;
    vector <int> dp(2 * m + 5 , 0);
    vector <int> g(2 * m + 5 , 0);
    vector < array<int,3> > v;
    vector <int> p;
    p.push_back(0);
    for (int i = 1 ; i <= m ; i ++) {
        array<int,3> tmp;
        cin >> tmp[0] >> tmp[1] >> tmp[2];
        int l = tmp[0] - tmp[1] + 1;
        int r = tmp[0];
        tmp[0] = r;
        tmp[1] = l;
        p.push_back(tmp[0]);
        p.push_back(tmp[1]);
        v.push_back(tmp);
    }
    sort(v.begin() , v.end());
    sort(p.begin() , p.end());
    p.erase(unique(p.begin(), p.end()), p.end());
    map<int,int>rk;
    for (int i = 1 ; i < p.size() ; i ++) {
        rk[p[i]] = i;
    }
    BIT bit(2 * m + 5);
    int id = 0;
    int sum = 0;
    for (int i = 1 ; i < p.size() ; i ++) {
        int now = p[i];
        while (id < m && v[id][0] == now) {
            bit.modify(rk[v[id][1]] + 1 , v[id][2]);
            sum += v[id][2];
            id++;
        }
        for (int j = i ; j >= 1 ; j --) {
            int last = p[j];
            int dif = now - last + 1;
            if (dif > k) {
                break;
            }
            int del = dif * d;
            int add = sum - bit.query(rk[last]);
            //cout << i << "  " << j << " " << bit.query(j) << endl;
            if (j == 1 || p[j - 1] + 1 != p[j])
                dp[i] = max(dp[i] , g[max(j - 1 , 0LL)] + add - del);
            else
                dp[i] = max(dp[i] , g[max(j - 2 , 0LL)] + add - del);
        }
        g[i] = max(g[i - 1] , dp[i]);
    }
    cout << g[p.size() - 1] << endl;
}
/**   懒标记线段树（LazySegmentTree）
 *    2023-03-03: https://atcoder.jp/contests/joi2023yo2/submissions/39363123
 *    2023-03-12: https://codeforces.com/contest/1804/submission/197106837
 *    2023-07-17: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=62804432
 *    2023-11-12: https://qoj.ac/submission/249505
 *    2024-08-14:  https://ac.nowcoder.com/acm/contest/view-submission?submissionId=70980889&returnHomeType=1&uid=329687984
**/
template<class Info, class Tag>
struct LazySegmentTree {
    int n;
    vector<Info> info;
    vector<Tag> tag;
    LazySegmentTree() : n(0) {}
    LazySegmentTree(int n_) { init(n_); }

    
    void init(int n_) {
        n = n_;
        info.assign(4 * n + 5, Info());
        tag.assign(4 * n + 5, Tag());
    }

    inline void pull(int p) { info[p] = info[p << 1] + info[p << 1 | 1]; }

    inline void apply(int p, const Tag &v) {
        info[p].apply(v);
        tag[p].apply(v);
    }

    inline void push(int p) {
        if (tag[p].x == 0) return;
        apply(p << 1, tag[p]);
        apply(p << 1 | 1, tag[p]);
        tag[p] = Tag();
    }

    void modify(int p, int l, int r, int x, const Info &v) {
        if (r - l == 1) { info[p] = v; return; }
        int m = (l + r) >> 1;
        push(p);
        if (x < m) modify(p << 1, l, m, x, v);
        else modify(p << 1 | 1, m, r, x, v);
        pull(p);
    }
    inline void modify(int pos, const Info &v) { modify(1, 0, n, pos, v); }

    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l >= y || r <= x) return Info();
        if (l >= x && r <= y) return info[p];
        int m = (l + r) >> 1;
        push(p);
        return rangeQuery(p << 1, l, m, x, y) + rangeQuery(p << 1 | 1, m, r, x, y);
    }
    inline Info rangeQuery(int l, int r) { return rangeQuery(1, 0, n, l, r); }

    void rangeApply(int p, int l, int r, int x, int y, const Tag &v) {
        if (l >= y || r <= x) return;
        if (l >= x && r <= y) { apply(p, v); return; }
        int m = (l + r) >> 1;
        push(p);
        rangeApply(p << 1, l, m, x, y, v);
        rangeApply(p << 1 | 1, m, r, x, y, v);
        pull(p);
    }
    inline void rangeApply(int l, int r, const Tag &v) { rangeApply(1, 0, n, l, r, v); }
};

struct Tag {
    int x = 0;
    inline void apply(const Tag &t) & { x += t.x; }
};

struct Info {
    int x = 0;
    inline void apply(const Tag &t) & { x += t.x; }
};

inline Info operator+(const Info &a, const Info &b) { return {max(a.x, b.x)}; }


void solve_mlogm() {
    int n, m, k, d;
    cin >> n >> m >> k >> d;

    vector<array<int,3>> v;
    v.reserve(m);

    vector<int> p;
    p.reserve(2 * m + 1);
    p.push_back(0);

    for (int i = 1; i <= m; i++) {
        int x, y, w;
        cin >> x >> y >> w;
        int l = x - y + 1;
        int r = x;
        v.push_back({r, l, w});
        p.push_back(r);
        p.push_back(l);
    }

    sort(v.begin(), v.end());
    sort(p.begin(), p.end());
    p.erase(unique(p.begin(), p.end()), p.end());

    const int S = (int)p.size(); 

    vector<int> g(S + 1, 0);
    vector<int> dp(S + 1, 0);

    unordered_map<int,int> rk;
    rk.reserve(S * 2);
    rk.max_load_factor(0.7f);
    for (int i = 0; i < S; i++) rk[p[i]] = i;

    LazySegmentTree<Info, Tag> seg(S + 2);

    int id = 0;
    int lptr = 1;

    for (int i = 1; i < S; i++) {
        if (i == 1 || p[i - 1] + 1 != p[i]) seg.modify(i, {g[i - 1] - d});
        else seg.modify(i, {g[i - 2] - d});

        int now = p[i];
        
        seg.rangeApply(1, i, {(p[i - 1] - p[i]) * d});

        while (id < m && v[id][0] == now) {
            seg.rangeApply(1, rk[v[id][1]] + 1, {v[id][2]});
            id++;
        }

        while (lptr < i && p[i] - p[lptr] >= k) lptr++;

        dp[i] = seg.rangeQuery(lptr, i + 1).x;
        g[i] = max(g[i - 1], dp[i]);
    }

    cout << g[S - 1] << '\n';
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    int c , t;
    cin >> c >> t;
    while (t--) {
        solve_mlogm();
    }
}