思路与算法

把每个可完成挑战写成区间[l=x-y+1,r=x]，y>k者永不触发可删除。最优连续跑步段可以从某个挑战的左端开始，否则删去无贡献前缀更优，因此压缩所有l-1及r和0。线段树下标j表示最近休息日，值为之前已休息的最优收益，减去从j到当前日的跑步成本，加上当前这段内完全覆盖的已结束挑战奖励。按事件日递增：全体减d*天数差，插入当天休息状态为先前best，对结束于当天的挑战给j≤l-1区间加v，查询j≥当前日-k且j<当前日的最大值并更新best。

正确性说明

任一合法安排可分为休息分隔的跑步段。固定最后休息日j后，后面每天跑步，成本和挑战奖励完全由j与当前日决定，状态无需保留更早细节；此前状态的最优收益可独立拼接。挑战在结束日恰对j<l的所有状态贡献，区间加准确。j下界保证连续不超过k天，排除当天休息点防止休息同时领奖。最优段首可缩到首个已领奖挑战的左端，故压缩坐标包含必要断点；全体减费用处理空白天不会漏计。取历史best也涵盖随时停止或从不跑步。

复杂度

每组O(m log m)时间、O(m)空间，含排序、去重及线段树初始化；T组总O(∑m log m)。

易错点

每天成本是d，不是仅发生挑战的那几天付费；休息至少一天才能重置连续天数。能量可负，但全不跑答案0始终可行。天数乘费用最高1e18，用64位并保留安全负无穷。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll NEG = -(1LL << 61);
struct Seg {
    int n;
    vector<ll> mx, lz;
    Seg(int n) : n(n), mx(4 * n, NEG), lz(4 * n) {
    }
    void apply(int u, ll v) {
        mx[u] += v;
        lz[u] += v;
    }
    void push(int u) {
        if (lz[u]) {
            apply(2 * u, lz[u]);
            apply(2 * u + 1, lz[u]);
            lz[u] = 0;
        }
    }
    void add(int u, int l, int r, int L, int R, ll v) {
        if (L <= l && r <= R) {
            apply(u, v);
            return;
        }
        push(u);
        int m = (l + r) / 2;
        if (L <= m)
            add(2 * u, l, m, L, R, v);
        if (R > m)
            add(2 * u + 1, m + 1, r, L, R, v);
        mx[u] = max(mx[2 * u], mx[2 * u + 1]);
    }
    void setval(int u, int l, int r, int p, ll v) {
        if (l == r) {
            mx[u] = v;
            lz[u] = 0;
            return;
        }
        push(u);
        int m = (l + r) / 2;
        if (p <= m)
            setval(2 * u, l, m, p, v);
        else
            setval(2 * u + 1, m + 1, r, p, v);
        mx[u] = max(mx[2 * u], mx[2 * u + 1]);
    }
    ll query(int u, int l, int r, int L, int R) {
        if (L > R)
            return NEG;
        if (L <= l && r <= R)
            return mx[u];
        push(u);
        int m = (l + r) / 2;
        ll v = NEG;
        if (L <= m)
            v = max(v, query(2 * u, l, m, L, R));
        if (R > m)
            v = max(v, query(2 * u + 1, m + 1, r, L, R));
        return v;
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int c, T;
    cin >> c >> T;
    while (T--) {
        int n, m, k;
        ll d;
        cin >> n >> m >> k >> d;
        struct Event {
            int r, l;
            ll v;
        };
        vector<Event> events;
        vector<int> pos{0};
        for (int i = 0; i < m; i++) {
            int x, y;
            ll v;
            cin >> x >> y >> v;
            if (y <= k) {
                events.push_back({x, x - y + 1, v});
                pos.push_back(x);
                pos.push_back(x - y);
            }
        }
        sort(events.begin(), events.end(), [](Event a, Event b) {
            return a.r < b.r;
        });
        sort(pos.begin(), pos.end());
        pos.erase(unique(pos.begin(), pos.end()), pos.end());
        int N = pos.size(), at = 0, last = 0;
        ll best = 0;
        Seg tree(N);
        for (int i = 0; i < N; i++) {
            int t = pos[i];
            tree.apply(1, -d * (t - last));
            tree.setval(1, 0, N - 1, i, best);
            while (at < (int)events.size() && events[at].r == t) {
                auto e = events[at++];
                int R = upper_bound(pos.begin(), pos.end(), e.l - 1) - pos.begin() - 1;
                tree.add(1, 0, N - 1, 0, R, e.v);
            }
            int L = lower_bound(pos.begin(), pos.end(), t - k) - pos.begin();
            if (L < i)
                best = max(best, tree.query(1, 0, N - 1, L, i - 1));
            last = t;
        }
        cout << best << "\n";
    }
}