洛谷P9871 [NOIP2023] 天天爱打卡题解

题目链接：P9871 [NOIP2023] 天天爱打卡

题意：

小 T 同学非常热衷于跑步。为了让跑步更加有趣，他决定制作一款叫做《天天爱打卡》的软件，使得用户每天都可以进行跑步打卡。

开发完成后，小 T 同学计划进行试运行，他找了大 Y 同学来帮忙。试运行共 \(n\) 天，编号为从 \(1\) 到 \(n\)。

对大 Y 同学来说，如果某天他选择跑步打卡，那么他的能量值会减少 \(d\)。初始时，他的能量值是 \(0\)，并且试运行期间他的能量值可以是负数。

而且大 Y 不会连续跑步打卡超过 \(k\) 天；即不能存在 \(1\le x\le n-k\)，使得他在第 \(x\) 到第 \(x+k\) 天均进行了跑步打卡。

小 T 同学在软件中设计了 \(m\) 个挑战，第 \(i\)（\(1\le i \le m\)）个挑战可以用三个正整数 \((x_i,y_i,v_i)\) 描述，表示如果在第 \(x_i\) 天时，用户已经连续跑步打卡至少 \(y_i\) 天（即第 \(x_i-y_i+1\) 到第 \(x_i\) 天均完成了跑步打卡），那么小 T 同学就会请用户吃饭，从而使用户的能量值提高 \(v_i\)。

现在大 Y 想知道，在软件试运行的 \(n\) 天结束后，他的能量值最高可以达到多少？

输入格式：

本题的测试点包含有多组测试数据。

输入的第一行包含两个整数 \(c\) 和 \(t\)，分别表示测试点编号和测试数据组数。对于样例，\(c\) 表示该样例与测试点 \(c\) 拥有相同的限制条件。

接下来，对于每组测试数据：

输入的第一行包含四个正整数 \(n,m,k,d\)，分别表示试运行的天数、挑战的个数、大 Y 单次跑步打卡的连续天数限制以及大 Y 跑步打卡减少的能量值。

接下来 \(m\) 行，每行包含三个正整数 \(x_i,y_i,v_i\)，表示一次挑战。

输出格式：

输出一行一个整数表示对应的答案。

数据范围：

记 \(l_i=x_i-y_i+1\)，\(r_i=x_i\)；

\(1\le t\le 10\)，\(1\le k\le n\le 10^9,~1\le m\le 10^5,~1\le l_i\le r_i\le n,~1\le d,v_i\le 10^9\)。

设 \(f_{i,0/1}\) 为第 \(i\) 天跑不跑时的最大收益，则 \[ \begin{aligned} f_{i,0} &= \max_{j < i} \left\{f_{j, 1}\right\} \\ f_{i, 1} &= \max_{ i - k \le j < i } \left\{ f_{j, 0} + d\times j + \sum_{j < l_p \le r_p \le i} v_p\right\} - d\times i \end{aligned} \] \(f_{i,0}\) 可以 \(\mathcal{O}(1)\) 维护，而 \(f_{i,1}\) 比较麻烦的在于 \(\sum_{j < l_p \le r_p \le i} v_p\) 怎么维护。

考虑把线段按 \(r\) 排序，这样每次只需要处理 \(r_p=i\) 的线段

注意到一条线段 \((l_p,i)\) 能对所有 \(j < l_p\) 的 \(j\) 产生贡献，或者说使得 \(f_{j,0} \gets f_{j,0} + v_p\) 。

前面的 \(f_{j,0}\) 已经是区间 Max 了，很容易想到这个线段就是一个区间加法，考虑线段树维护这个 \(f_{j,0}\) 。

然后因为我们不会在没有线段的烂区间里跑，所以有用的 \(i\) ，或者说决策点只可能是 \(l_p - 1\) 和 \(r_p\) 。

考虑对所有线段的端点离散化一下，这样复杂度就是 \(\mathcal{O}(m \log m)\) 的。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(2e5 + 15))
#define ls(at) ((at) << 1)
#define rs(at) ((at) << 1 | 1)

struct line { int l, r, v; } a[N];
struct node { int mx, tag; } tr[N * 4];
int n, m, k, d, b[N], f[N];
void push_up(int at) { up(tr[at].mx = tr[ls(at)].mx, tr[rs(at)].mx); }
void proc(int at, int v) { tr[at].mx += v; tr[at].tag += v; }
void push_down(int at)
{ 
    proc(ls(at), tr[at].tag);
    proc(rs(at), tr[at].tag); tr[at].tag = 0;
}
void build(int at, int l, int r)
{
    tr[at].tag = 0;
    if(l == r) return tr[at].mx = l ? -INF : 0, void(0);
    push_down(at); int mid = (l + r) >> 1;
    build(ls(at), l, mid); build(rs(at), mid + 1, r); push_up(at);
}
void Modify(int x, int v, int at = 1, int l = 0, int r = n)
{
    if(l == r) return tr[at].mx = v, void(0);
    push_down(at); int mid = (l + r) >> 1;
    if(x <= mid) Modify(x, v, ls(at), l, mid);
    else Modify(x, v, rs(at), mid + 1, r);
    push_up(at);
}
void update(int nl, int nr, int v, int at = 1, int l = 0, int r = n)
{
    if(nl <= l && r <= nr) return proc(at, v);
    push_down(at); int mid = (l + r) >> 1;
    if(nl <= mid) update(nl, nr, v, ls(at), l, mid);
    if(nr > mid) update(nl, nr, v, rs(at), mid + 1, r);
    push_up(at);
}
int query(int nl, int nr, int at = 1, int l = 0, int r = n)
{
    if(nl <= l && r <= nr) return tr[at].mx;
    push_down(at); int mid = (l + r) >> 1, mx = -INF;
    if(nl <= mid) up(mx, query(nl, nr, ls(at), l, mid));
    if(nr > mid) up(mx, query(nl, nr, rs(at), mid + 1, r));
    return mx;
}
void solve()
{
    cin >> n >> m >> k >> d; int cnt = 0;
    for(int i = 1; i <= m; i++)
    {
        cin >> a[i].r >> a[i].l >> a[i].v;
        a[i].l = a[i].r - a[i].l; b[++cnt] = a[i].l; b[++cnt] = a[i].r;
    }
    sort(b + 1, b + 1 + cnt); cnt = unique(b + 1, b + 1 + cnt) - b - 1;
    for(int i = 1; i <= m; i++)
    {
        a[i].l = lower_bound(b + 1, b + 1 + cnt, a[i].l) - b;
        a[i].r = lower_bound(b + 1, b + 1 + cnt, a[i].r) - b;
    }
    sort(a + 1, a + 1 + m, [](line a, line b) { return a.r < b.r; });
    n = cnt; build(1, 0, n); int mx = 0; 
    for(int i = 1, p = 1, j = 0; i <= n; i++)
    {
        Modify(i, mx + d * b[i]);
        while(p <= m && a[p].r == i) { update(0, a[p].l, a[p].v), ++p; }
        while(j < i && b[j] < b[i] - k) ++j;
        f[i] = j < i ? (query(j, i - 1) - d * b[i]) : -INF; up(mx, f[i]);
    }
    // for(int i = 1; i <= n; i++) cout << f[i] << " \n"[i == n];
    cout << mx << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int qwq, _; cin >> _ >> qwq; while(qwq--) solve();
    return 0;
}