题解

「ROI 2025 Day2 T4」程序员生活 题解

题目分析

我们需要将 $n$ 集电视剧分成 $k$ 天播放，使得每天的吸引力指数序列字典序最小。每天的吸引力指数是当天播放剧集中排名最差的（数值最大的）。

关键观察

1. 字典序最小策略：

   • 要让 $b_1$ 最小，第一天应该包含尽可能多的剧集，但不能包含排名太差的剧集
   • 在 $b_1$ 固定的情况下，再优化 $b_2$，依此类推

2. 单调性：使用单调栈预处理每个位置右边第一个更大的元素位置

3. RMQ 优化：快速查询区间最小/最大值的位置

算法思路

1. 预处理阶段

单调栈计算右边界

for (int i = 0; i <= n + 1; stk.push(i++)) {
    while (stk.size()) {
        int top = stk.top();
        if (a[top] < a[i]) ri[top] = i, stk.pop();
        else break;
    }
}

计算每个位置右边第一个比它大的位置，用于确定分割点。

后缀最大值

for (int i = n; i; i--) suf[i] = max(suf[i + 1], a[i]);

用于处理最后一天的答案。

界限预处理

for (int i = 1; i <= n; i++) {
    int l = i + 1, r = ri[i] + 1;
    // 二分查找确定 lim[i]
}

预处理每个位置的分割界限。

2. 查询处理

分段维护最优解

for (int k = 2; k < n; k++) {
    // 维护 seg 数组，每个段表示 [l, r] 区间内使用相同的策略
    while (c && (seg[c].v > n - k))
        t = seg[c--].l - 1;
    
    // 添加新的段
    for (int i = t; i < k; i++) {
        // 根据条件创建新的段
    }
}

回答查询

for (int i : qry[k]) {
    int t = min(qi[i], k - 1);
    // 二分找到对应的段
    int l = 0, r = c + 1;
    while (l + 1 < r) {
        int mid = (l + r) >> 1;
        (seg[mid].r < t) ? (l = mid) : (r = mid);
    }
    // 计算答案
    int res = seg[r].v + t;
    if (qi[i] < k) ans[i] = a[res];
    else ans[i] = suf[min(ri[res], n)];
}

算法复杂度

• 预处理：$O(n \log n)$（单调栈 + ST表构建）
• 查询处理：$O((n + q) \log n)$
• 总复杂度：$O((n + q) \log n)$，可以处理 $n, q \le 3 \times 10^5$ 的数据

算法优势

1. 高效预处理：利用单调栈和 ST 表快速获取区间信息
2. 分段优化：将解空间分成若干段，避免重复计算
3. 离线处理：按 $k$ 分组查询，批量处理
4. 边界处理：特殊处理 $k=1$ 和 $k=n$ 的情况

总结

本题通过巧妙的预处理和分段维护技术，结合单调栈和 RMQ 优化，高效解决了电视剧播放安排的优化问题。算法在保证字典序最优的同时，能够快速回答大量查询。

最终算法标签： 单调栈 RMQ 稀疏表 分段处理 二分查找 贪心算法 离线查询