「KTSC 2024 R2」跳跃游戏 题解

问题分析

我们需要在一个长度为 $N$（可达 $10^{12}$）的数组上，通过区间加操作构建数组 $A$，然后找到从位置 $0$ 到超过 $N-1$ 的最优路径，其中：

• 可以走一步（$i \to i+1$，不加分）
• 可以跳跃（$i \to i+K$，加 $A[i]$ 分）

目标是最大化总得分。

算法思路：动态规划 + 平衡树优化

核心观察

设 $dp[i]$ 表示到达位置 $i$ 时的最大得分，则状态转移为：

但由于 $N$ 太大，不能直接存储所有 $dp$ 值。

1. 关键数据结构：平衡树维护分段函数

int lc[_], rc[_], cnt, rt;      // 平衡树结构
ll sl[_], sr[_], sv[_], tg[_];  // 区间左端点、右端点、值、懒标记

int apply(ll l, ll r, ll v) {
    // 创建新节点表示区间[l,r]的dp值为v
    int p = ++cnt;
    sl[p] = l; sr[p] = r; sv[p] = v;
    tg[p] = 0; lc[p] = rc[p] = 0;
    prio[p] = rng();  // 随机优先级维护平衡
    return p;
}

设计原理：由于 $dp$ 函数是分段线性的，用平衡树维护这些分段。

2. 平衡树操作

分裂操作

void split_p(int p, ll v, int &x, int &y) {
    int q = split_pos(p, v, x, y);
    if (!q) return;
    // 在位置v处分割区间
    x = merge(x, apply(ql, v-1, qv));
    y = merge(apply(v, qr, qv), y);
}

合并操作

int merge(int x, int y) {
    if (!x || !y) return x | y;
    pushdown(x); pushdown(y);
    if (prio[x] < prio[y])
        return rc[x] = merge(rc[x], y), x;
    else
        return lc[y] = merge(x, lc[y]), y;
}

3. 核心算法流程

预处理区间操作

vl buc;
buc.emplace_back(N-1);
buc.emplace_back(N);
for (int i = 0; i < Q; ++i) {
    L[i] = N - L[i] - 1, R[i] = N - R[i];  // 坐标转换
    buc.emplace_back(L[i]);
    buc.emplace_back(R[i]);
}
sort(ALL(buc));
buc.erase(unique(ALL(buc)), buc.end());

目的：将所有关键点（区间端点）提取出来，将问题离散化。

主循环处理

while (x < sz) {
    if (cur + K <= buc[x]) {
        // 可以连续跳跃多次
        ll c = (buc[x] - cur) / K;
        proc(rt, val * c);           // 批量更新dp值
        update(lim + val * (c-1));   // 更新限制
        lim = sv[getmx(rt)];
        cur += c * K;
    }
    
    // 处理当前K范围内的区间
    for (int i = y-1; i >= x; --i) {
        split_p(rt, buc[i]-cur, rt, now);
        proc(now, s[i]);            // 应用区间加操作
        fusion(now, nrt);
    }
    
    proc(rt, val);
    fusion(rt, nrt);
    rt = nrt;
    update(lim);
    
    if (y >= sz || buc[y] >= N)
        return query(N-1-cur, rt);   // 到达终点
}

4. 状态转移的实现

走一步操作

proc(rt, val);  // 所有dp值增加val，相当于i->i+1

跳跃操作

// 通过分裂合并，将i-K位置的dp值加上A[i]后与当前位置取max
fusion(now, nrt);  // 合并时自动取最大值

限制更新

void update(ll lim) {
    int tmp;
    split_v(rt, lim, tmp, rt);  // 按值分裂
    if (tmp) {
        rt = merge(apply(0, sr[getmx(tmp)], lim), rt);
        crush(tmp);  // 丢弃旧区间
    }
}

作用：确保dp值的单调性，移除不可能成为最优解的状态。

5. 最终答案查询

return query(N-1-cur, rt);  // 查询终点位置的dp值

复杂度分析

• 预处理：$O(Q \log Q)$ 排序去重
• 主循环：每个关键区间 $O(\log Q)$ 平衡树操作
• 总复杂度：$O(Q \log Q)$，满足 $Q \leq 2.5 \times 10^5$ 的要求

关键优化技术

$1.$ 分段线性函数：利用dp函数的性质，用分段常数函数近似 $2.$ 懒标记：批量更新区间值 $3.$ 离散化：只处理关键点，避免 $O(N)$ 复杂度 $4.$ 平衡树：高效维护和更新分段函数

算法正确性

状态转移保证

• 走一步：所有dp值增加当前区间的A值
• 跳跃：将 $i-K$ 位置的dp值加上A[i]后取max
• 单调性：通过update操作维护dp值的单调不降性

边界处理

• 起点：$dp[0] = 0$
• 终点：查询 $dp[N-1]$ 或之后位置的值

该解法通过平衡树维护分段dp函数和离散化处理，高效解决了超大规模区间的动态规划问题。