题解：CEOI 2023 Day2 T1「Tricks of the Trade」

题目核心分析

问题本质

给定 $N$ 个机器人，每个机器人 $i$ 的购买成本为 $c_i$，出售价格为 $s_i$。要求选择一段连续的机器人序列（长度 $\geq K$），并从该序列中恰好选出 $K$ 个机器人出售，使得总利润（出售总收入 - 序列总购买成本）最大。同时需输出所有能参与最大利润方案的机器人（用 $01$ 串表示）。

关键公式

• 序列 $[l, r]$（$r - l + 1 \geq K$）的总购买成本：$\sum_{i=l}^r c_i$（用前缀和 $sum[r] - sum[l-1]$ 快速计算）；
• 序列 $[l, r]$ 中选择 $K$ 个机器人出售的最大总收入：$\sum_{i \in top-K(s[l..r])} s_i$（即序列中 $s_i$ 前 $K$ 大的元素和）；
• 利润公式：$\text{profit}(l, r) = \text{top-K-sum}(l, r) - (sum[r] - sum[l-1])$。

核心目标

1. 找到所有满足 $r - l + 1 \geq K$ 的区间 $[l, r]$ 中，$\text{profit}(l, r)$ 的最大值；
2. 标记所有能出现在任意一个最大利润区间中的机器人（即该机器人在某个最优区间的前 $K$ 大 $s_i$ 中）。

算法设计

整体思路

采用「分治优化 + 动态开点线段树」的组合算法，同时针对小数据提供暴力 DP 兜底，确保时间复杂度适配 $N \leq 2.5 \times 10^5$ 的大数据范围。

1. 小数据处理（$N \leq 6000$ 或 $K \leq 200$）

使用前后缀 DP 暴力枚举所有可能方案，保证正确性的同时快速拿分：

• 前缀 DP：$dp[i][j]$ 表示前 $i$ 个机器人中选 $j$ 个出售，且包含第 $i$ 个机器人的最小成本（等价于最大利润的反向计算）；
• 后缀 DP：$f[i][j]$ 表示后 $n - i + 1$ 个机器人中选 $j$ 个出售，且包含第 $i$ 个机器人的最小成本；
• 合并前后缀 DP 结果，判断每个机器人是否能参与最优方案。

2. 大数据处理（无附加限制）

核心优化：分治找最优区间

利用「最优区间的单调性」（左端点固定时，最优右端点单调递增），通过分治算法减少无效枚举：

• 分治函数 solve(l, r, ql, qr)：处理右端点范围 $[l, r]$，且对应的最优左端点范围为 $[ql, qr]$；
• 对当前中点 $mi$（右端点），枚举左端点 $i \in [ql, \min(mi-K+1, qr)]$，找到使 $\text{profit}(i, mi)$ 最大的左端点 $best$；
• 递归处理左半区间 $[l, mi-1]$（左端点范围 $[ql, best]$）和右半区间 $[mi+1, r]$（左端点范围 $[best, qr]$），时间复杂度 $O(N \log N)$。

数据结构：动态开点线段树（离散化 + 前缀树）

用于快速查询区间 $[l, r]$ 的前 $K$ 大 $s_i$ 和、第 $K$ 大 $s_i$：

1. 离散化：由于 $s_i \leq 10^9$，直接建树空间不足，先对所有 $s_i$ 排序去重，映射为离散化后的编号（范围 $1 \sim cnt$）；
2. 前缀线段树：每个 $root[i]$ 对应前 $i$ 个机器人的离散化 $s_i$ 构建的动态开点线段树，存储两个信息：
   • $\text{sum}$：该节点对应离散化区间内的 $s_i$ 总和；
   • $\text{num}$：该节点对应离散化区间内的元素个数；
3. 区间查询：通过 $root[r] - root[l-1]$ 得到区间 $[l, r]$ 的线段树，查询前 $K$ 大元素和（右子树优先查询，优先取大值）。

方案标记：区间修改线段树

用于标记所有最优区间中前 $K$ 大 $s_i$ 的最小值：

• 对每个最优区间 $[l, r]$，查询其第 $K$ 大 $s_i$（记为 $v$）；
• 用区间修改线段树将 $[l, r]$ 区间的标记值更新为 $\min$（当前标记值，$v$）；
• 最终，若机器人 $i$ 的 $s_i \geq$ 其对应的标记值，则 $i$ 能参与最优方案（输出 $1$）。

算法步骤详解

1. 预处理

• 计算 $c$ 数组的前缀和 $sum$，用于快速计算区间购买成本；
• 对 $s$ 数组离散化，构建前缀动态开点线段树 $root$。

2. 分治找最优区间

• 调用 solve(K, N, 1, N)，枚举所有合法右端点 $[K, N]$（因区间长度 $\geq K$）；
• 记录所有最优区间 $[l, r]$（利润等于最大利润）。

3. 标记最优机器人

• 对每个最优区间 $[l, r]$，查询其第 $K$ 大 $s_i$，用区间修改线段树更新 $[l, r]$ 的标记值；
• 遍历每个机器人，若其 $s_i \geq$ 标记值，则输出 $1$，否则输出 $0$。

4. 小数据兜底（$N \leq 6000$ 或 $K \leq 200$）

• 前缀 DP 初始化：$dp[0][0] = 0$，$dp[0][j>0] = -\inf$；
• 前缀 DP 转移：
  • $dp[i][j] = dp[i-1][j] - c[i]$（不选第 $i$ 个机器人出售，仅购买）；
  • $dp[i][j] = \max(dp[i][j], dp[i-1][j-1] - c[i] + s[i])$（选第 $i$ 个机器人出售）；
• 后缀 DP 同理，反向遍历计算 $f[i][j]$；
• 合并判断：机器人 $i$ 能参与最优方案，当且仅存在 $left$ 使得 $dp[i-1][left] + f[i+1][K-1-left] - c[i] + s[i] = \text{max_profit}$。

代码逐段解析

1. 数据结构定义

const int N = 3e5 + 10, inf = 1e18;
int n, k, c[N], s[N];
vector<int> dp[N], f[N];  // 小数据 DP 数组
int sum[N];  // c 数组前缀和
int ls[N], cnt;  // 离散化数组及去重后长度
// 动态开点线段树节点：sum（元素和）、num（元素个数）、左右孩子
struct node { int sum, num, ls, rs; } tr[N * 64];
int Cnt;  // 动态开点线段树节点计数
int root[N];  // 前缀线段树根节点
int mn[N << 2];  // 区间修改线段树（存储最优区间第 K 大的最小值）
vector<pair<int, int>> vc;  // 存储所有最优区间 [l, r]
int Dp[N], pos[N];  // Dp[mi]：右端点为 mi 时的最大利润；pos[mi]：对应最优左端点

2. 动态开点线段树操作

（1）更新（插入元素）

void pushup(int p) {
    tr[p].sum = tr[tr[p].ls].sum + tr[tr[p].rs].sum;
    tr[p].num = tr[tr[p].ls].num + tr[tr[p].rs].num;
}
void update(int pre, int &p, int k, int L, int R) {
    p = ++Cnt;
    tr[p] = tr[pre];  // 继承前一个版本
    if (L == R) {
        tr[p].sum++;  // 元素个数 +1
        tr[p].num += ls[k];  // 元素和 += 离散化前的 s_i（ls[k] 是原数值）
        return;
    }
    int mi = (L + R) >> 1;
    if (k <= mi) update(tr[pre].ls, tr[p].ls, k, L, mi);
    else update(tr[pre].rs, tr[p].rs, k, mi + 1, R);
    pushup(p);
}

（2）查询区间前 K 大元素和

int query(int lp, int rp, int k, int L, int R) {
    if (L == R) return min(tr[rp].sum - tr[lp].sum, k) * ls[L];
    int mi = (L + R) >> 1;
    int nu = tr[tr[rp].rs].sum - tr[tr[lp].rs].sum;  // 右子树元素个数（大值区域）
    if (nu < k) {
        // 右子树元素不足 K 个，取右子树全部，左子树补 K - nu 个
        return (tr[tr[rp].rs].num - tr[tr[lp].rs].num) + query(tr[lp].ls, tr[rp].ls, k - nu, L, mi);
    } else {
        // 右子树元素足够，直接在右子树查询
        return query(tr[lp].rs, tr[rp].rs, k, mi + 1, R);
    }
}

（3）查询区间第 K 大元素

int kth(int lp, int rp, int k, int L, int R) {
    if (L == R) return ls[L];  // 离散化还原为原数值
    int mi = (L + R) >> 1;
    int nu = tr[tr[rp].rs].sum - tr[tr[lp].rs].sum;
    if (nu < k) return kth(tr[lp].ls, tr[rp].ls, k - nu, L, mi);
    else return kth(tr[lp].rs, tr[rp].rs, k, mi + 1, R);
}

3. 分治找最优区间

int calc(int l, int r) {
    if (r - l + 1 < k) return -inf;  // 区间长度不足 K，非法
    // 前 K 大 s_i 和 - 区间购买成本
    return query(root[l-1], root[r], k, 1, cnt) - (sum[r] - sum[l-1]);
}
void solve(int l, int r, int ql, int qr) {
    if (l > r) return;
    int mi = (l + r) >> 1;  // 当前右端点
    int best = ql;
    // 枚举合法左端点，找最大利润对应的左端点
    for (int i = ql; i <= min(mi - k + 1, qr); i++) {
        if (calc(i, mi) > calc(best, mi)) best = i;
    }
    pos[mi] = best;
    Dp[mi] = calc(best, mi);
    // 记录所有利润等于当前最大值的区间
    for (int i = ql; i <= min(mi - k + 1, qr); i++) {
        if (calc(i, mi) == Dp[mi]) vc.emplace_back(i, mi);
    }
    // 分治递归
    solve(l, mi - 1, ql, pos[mi]);
    solve(mi + 1, r, pos[mi], qr);
}

4. 区间修改线段树（标记最优区间）

// 区间修改：将 [l, r] 区间的最小值更新为 k
void upd(int l, int r, int k, int p, int L, int R) {
    if (L > r || R < l) return;
    if (L >= l && R <= r) {
        mn[p] = min(mn[p], k);
        return;
    }
    int mi = (L + R) >> 1;
    upd(l, r, k, p << 1, L, mi);
    upd(l, r, k, p << 1 | 1, mi + 1, R);
}
// 单点查询：查询位置 l 的最小值
int query(int l, int p, int L, int R) {
    if (L == R) return mn[p];
    int mi = (L + R) >> 1;
    int res = mn[p];
    if (l <= mi) res = min(res, query(l, p << 1, L, mi));
    else res = min(res, query(l, p << 1 | 1, mi + 1, R));
    return res;
}

5. 小数据 DP 处理

if (n <= 6000 || k <= 200) {
    // 前缀 DP 初始化
    dp[0].resize(k + 1);
    for (int i = 1; i <= k; i++) dp[0][i] = -inf;
    dp[0][0] = 0;
    int ans = -inf;
    // 前缀 DP 转移
    for (int i = 1; i <= n; i++) {
        dp[i].resize(k + 1);
        dp[i][0] = 0;
        for (int j = 1; j <= k; j++) {
            dp[i][j] = dp[i-1][j] - c[i];  // 不选第 i 个出售
            dp[i][j] = max(dp[i][j], dp[i-1][j-1] - c[i] + s[i]);  // 选第 i 个出售
        }
        ans = max(ans, dp[i][k]);
    }
    // 后缀 DP 初始化
    f[n+1].resize(k + 1);
    for (int i = 1; i <= k; i++) f[n+1][i] = -inf;
    f[n+1][0] = 0;
    // 后缀 DP 转移
    for (int i = n; i; i--) {
        f[i].resize(k + 1);
        f[i][0] = 0;
        for (int j = 1; j <= k; j++) {
            f[i][j] = f[i+1][j] - c[i];
            f[i][j] = max(f[i][j], f[i+1][j-1] - c[i] + s[i]);
        }
    }
    // 输出结果
    cout << ans << '\n';
    for (int i = 1; i <= n; i++) {
        bool fl = 0;
        // 检查是否存在 left 使得 i 参与最优方案
        for (int left = 0; left + 1 <= k; left++) {
            fl |= (dp[i-1][left] + f[i+1][k-1-left] - c[i] + s[i]) == ans;
        }
        cout << fl;
    }
    exit(0);
}

6. 主函数（大数据流程）

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    memset(mn, 0x3f, sizeof mn);  // 区间修改线段树初始化为无穷大
    cin >> n >> k;

    // 小数据处理（上述代码块）

    // 大数据预处理：前缀和 + 离散化 + 前缀线段树
    for (int i = 1; i <= n; i++) {
        cin >> c[i];
        sum[i] = sum[i-1] + c[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        ls[++cnt] = s[i];  // 收集 s 数组用于离散化
    }
    // 离散化：排序 + 去重
    sort(ls + 1, ls + 1 + cnt);
    cnt = unique(ls + 1, ls + 1 + cnt) - ls - 1;
    // 构建前缀动态开点线段树
    for (int i = 1; i <= n; i++) {
        s[i] = lower_bound(ls + 1, ls + 1 + cnt, s[i]) - ls;  // s[i] 映射为离散化编号
        update(root[i-1], root[i], s[i], 1, cnt);
    }

    // 分治找最优区间
    solve(k, n, 1, n);
    // 计算最大利润
    int ans = -inf;
    for (int i = k; i <= n; i++) ans = max(ans, Dp[i]);
    cout << ans << '\n';

    // 标记最优区间的第 K 大 s_i
    for (auto [l, r] : vc) {
        if (calc(l, r) == ans) {  // 确认是最优区间
            int v = kth(root[l-1], root[r], k, 1, cnt);  // 第 K 大 s_i
            upd(l, r, v, 1, 1, n);  // 区间更新最小值
        }
    }

    // 输出 01 串
    for (int i = 1; i <= n; i++) {
        cout << (query(i, 1, 1, n) <= ls[s[i]]);  // s[i] 还原为原数值比较
    }
    return 0;
}

复杂度分析

时间复杂度

• 大数据分治：$O(N \log N)$（分治层数 $O(\log N)$，每层枚举 $O(N)$ 个区间，每个区间查询 $O(\log M)$，$M$ 为离散化后长度）；
• 动态开点线段树：单次插入/查询 $O(\log M)$，总复杂度 $O(N \log M)$；
• 区间修改线段树：单次修改/查询 $O(\log N)$，总复杂度 $O(N \log N)$；
• 小数据 DP：$O(NK)$，适配 $N \leq 6000$ 或 $K \leq 200$。

整体时间复杂度 $O(N \log N + N \log M)$，满足 $N \leq 2.5 \times 10^5$ 的数据范围。

空间复杂度

• 动态开点线段树：$O(N \log M)$（每个插入操作新增 $O(\log M)$ 个节点）；
• 其他数组：$O(N + K)$，整体空间复杂度 $O(N \log M)$，适配题目限制。