P9871 [NOIP2023] 天天爱打卡题解

题目大意

在 $n$ 天里，你可以选择一些天进行跑步打卡，不得连续跑步超过 $k$ 天，每次跑步消耗 $d$ 的能量值。

此外，有 $m$ 个任务。对于第 $i$ 个任务，若在第 $x_i$ 时，你已经连续打卡了 $y_i$ 天，就会获得 $v_i$ 的能量值，问 $n$ 天以后能量值最高是多少。

其中 $n\le 10^9$，$m\le 10^5$。

容易发现：开始 / 停止跑步的时间节点，一定是任务开始或是结束的时间点。这样，我们对跑步的天数进行离散化，时间复杂度中就不包含 $n$ 了。

考虑 DP，设 $f_i$ 表示从第一天开始，到第 $i$ 个时间节点为止，最多可以获得多少能量。我们可以枚举：到第 $i$ 个时间节点为止，已经连续跑步了多长时间。容易写出状态转移方程：

\[ f_i=\max_{num[j]\ge num[i]-k+1}\{g_j-(num[i]-num[j]+1)\times d+\sum_{p=1}^{m}{\big[[l_p,r_p]\subseteq[j,i]\big]\times v_p}\} \]

第 $i$ 个时间节点不跑步的情况：

\[ f_i=f_{i-1} \]

考虑到时间节点相邻的情况（即：在第 $j$ 天的前一天不能跑步；如果这样，连续跑步的时间可能超过 $k$），记 $g_j$ 表示满足 $num[k]<num[j]-1$ 的最大的 $f_k$。显然，由于 $f_i$ 单调递增，

\[ g_j= \begin{cases} f_{j-2},&num[j]=num[j-1]+1,\\ f_{j-1},&num[j]>num[j-1]+1 \end{cases} \]

上面提到的这种暴力转移的时间复杂度达到了 $O(n^3)$，需要优化。我们注意到 $[l_p,r_p]\subseteq [j,i]$ 貌似属于一种二维数点问题。我们借用扫描线的思想，将所有区间按 $r_p$ 排序，每遍历到一个 $i$，就把所有 $r_p=i$ 的区间在数据结构的 $l_p$ 处加上 $v_p$ 的权值。

这样，时间复杂度就被优化为 $O(n^2\log n)$，仍需进一步优化。

注意到，状态转移方程可以分解为和 $i$ 有关的部分（$-num[i]\times d$）以及和 $j$ 有关的部分（$g_j+(nun[j]-1)\times d+\sum_p v_p$）。其中后者的 $ \sum_p v_p$ 不易维护。但我们注意到，每次扫描线处理一个区间 $[l_p,r_p]$ 只对 $j\le l_p$ 有贡献，可以被刻画为一种区间修改。区修+区查最大值考虑线段树。

我们使用线段树维护 $g_j+(num[j]-1)\times d+\sum_p v_p$ 的区间最值：

新遍历到一个 $i$，需要处理 $\max\{\}$ 中新产生的的一项。我们分讨求出 $g_i$，并将 $g_i+(num[i]-1)\times d$ 单点修改到线段树的 $i$ 位置。
每次处理一个区间 $[l_p,r_p]$ 就在线段树上给区间 $[1,l_p]$ 加 $v_p$。
查询时，先用 lower_bound 找到第一个满足 $num[j]\ge num[i]-k+1$ 的 $j$，在线段树上查询 $[j,i]$ 的最大值，并加上 $-num[i]\times d$ 去更新 $f_i$。

技巧

可以考虑能贡献到查询操作的修改操作需满足什么条件，或能被修改操作贡献到的查询操作需要满足什么条件。
区间的包含关系通常可以被刻画为二维数点问题。

AC 代码

#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int N = 1E5 + 10;
const int INF = (int)0x3f3f3f3f3f3f3f3f;

struct Range {
    int l, r, v;
    inline bool operator<(const Range &other) const {
        return r < other.r;
    }
};

int tp, T;
int n, m, k, d;
int f[2 * N];
int num[2 * N], nn;
Range a[N];

namespace Seg_T {

    inline int lc(int x) { return x << 1; }
    inline int rc(int x) { return x << 1 | 1; }

    int mx[8 * N], tag[8 * N];

    inline void push_up(int p) {
        mx[p] = max(mx[lc(p)], mx[rc(p)]);
    }
    inline void move_tag(int p, int tg) {
        mx[p] += tg;
        tag[p] += tg;
    }
    inline void push_down(int p) {
        if(!tag[p]) return;
        move_tag(lc(p), tag[p]);
        move_tag(rc(p), tag[p]);
        tag[p] = 0;
    }

    void build(int p, int l, int r) {
        if(l == r) {
            mx[p] = (num[l] - 1) * d;
            return;
        }
        int mid = (l + r) >> 1;
        tag[p] = mx[p] = 0;
        build(lc(p), l, mid);
        build(rc(p), mid + 1, r);
        push_up(p);
    }
    void add(int p, int l, int r, int ql, int qr, int v) {
        if(ql <= l && r <= qr) {
            move_tag(p, v);
            return;
        }
        push_down(p);
        int mid = (l + r) >> 1;
        if(mid >= ql) add(lc(p), l, mid, ql, qr, v);
        if(mid < qr) add(rc(p), mid + 1, r, ql, qr, v);
        push_up(p);
    }
    void modify(int p, int l, int r, int q, int v) {
        if(l == r) {
            mx[p] = max(mx[p], v);
            return;
        }
        push_down(p);
        int mid = (l + r) >> 1;
        if(mid >= q) modify(lc(p), l, mid, q, v);
        else modify(rc(p), mid + 1, r, q, v);
        push_up(p);
    }
    int query(int p, int l, int r, int ql, int qr) {
        if(ql <= l && r <= qr) {
            return mx[p];
        }
        push_down(p);
        int mid = (l + r) >> 1;
        if(mid >= qr) return query(lc(p), l, mid, ql, qr);
        if(mid < ql) return query(rc(p), mid + 1, r, ql, qr);
        return max(query(lc(p), l, mid, ql, qr), query(rc(p), mid + 1, r, ql, qr));
    }

}

signed main() {

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> tp >> T;
    while(T--) {
        cin >> n >> m >> k >> d;
        nn = 0;
        for(int i = 1; i <= m; i++) {
            int x, y, v;
            cin >> x >> y >> v;
            a[i] = {x - y + 1, x, v};
            num[++nn] = a[i].l;
            num[++nn] = a[i].r;
        }
        sort(a + 1, a + 1 + m);
        sort(num + 1, num + 1 + nn);
        nn = unique(num + 1, num + 1 + nn) - (num + 1);
        for(int i = 1; i <= m; i++) {
            a[i].l = lower_bound(num + 1, num + 1 + nn, a[i].l) - num;
            a[i].r = lower_bound(num + 1, num + 1 + nn, a[i].r) - num;
        }
        f[0] = 0;
        Seg_T::build(1, 1, nn + 5);
        for(int i = 1, j = 1; i <= nn; i++) {
            // 处理新的一项
            if(i != 1) {
                if(num[i] == num[i - 1] + 1) {
                    if(i > 2) Seg_T::modify(1, 1, nn + 5, i, f[i - 2] + (num[i] - 1) * d);
                } else {
                    Seg_T::modify(1, 1, nn + 5, i, f[i - 1] + (num[i] - 1) * d);
                }
            }
            // 扫描线
            while(j <= m && a[j].r == i) {
                Seg_T::add(1, 1, nn + 5, 1, a[j].l, a[j].v);
                j++;
            }
            // 更新 f[i]
            int pre = lower_bound(num + 1, num + 1 + nn, num[i] - k + 1) - num;
            f[i] = max(f[i - 1], Seg_T::query(1, 1, nn + 5, pre, i) - num[i] * d);
        }
        cout << f[nn] << '\n';
    }

    return 0;
}

P9871 [NOIP2023] 天天爱打卡 题解

P9871 [NOIP2023] 天天爱打卡题解