「KTSC 2024 R1」最大化平均值 题解

问题分析

我们有一个序列操作问题：可以从一个"封闭序列"（两端小于中间）中移除中间的一些元素，目标是最大化最终序列的平均值。

关键观察：

• 封闭序列的性质：$A[i] < A[k]$ 且 $A[j] < A[k]$ 对所有 $i < k < j$ 成立
• 操作的本质：我们可以选择保留一些"峰值"，移除中间较小的值
• 最终序列必须保持原序列的两端 $A[i]$ 和 $A[j]$

核心思路

问题转化

对于封闭序列 $A[i..j]$，我们实际上是在寻找一个子序列 $A[i] = x_0, x_1, \ldots, x_{k-1}, x_k = A[j]$，使得平均值 $\frac{\sum x_t}{k+1}$ 最大。

这可以看作是在笛卡尔树上进行动态规划。

算法框架

1. 构建笛卡尔树：利用序列的封闭性质构建树结构
2. 树形DP：在笛卡尔树上进行分数规划
3. 平衡树优化：使用Treap维护凸壳，高效合并子树信息

代码详解

数据结构定义

struct vec {
    int x;    // 分母（元素个数）
    ll y;     // 分子（元素和）
    vec() = default;
    vec(int a, ll b): x(a), y(b) {}
};

vec operator + (const vec &a, const vec &b) {
    return vec(a.x + b.x, a.y + b.y);
}

bool operator < (const vec &a, const vec &b) {
    return a.y * b.x < b.y * a.x;  // 比较平均值 a.y/a.x < b.y/b.x
}

vec 结构表示一个分数，重载比较运算符用于比较平均值。

笛卡尔树构建

static int top, stk[N];
for (int i = 1; i <= n; i++) {
    for (; top && a[stk[top]] > a[i]; top--)
        ls[i] = stk[top];  // 构建左子树
    rs[stk[top]] = i;      // 构建右子树
    stk[++top] = i;
}

利用单调栈构建笛卡尔树，满足二叉搜索树和堆的性质。

Treap操作

void split(int rt, vec val, int &x, int &y) {
    if (!rt) return x = y = 0, void();
    if (t[rt].val < val)  // 按平均值分裂
        y = rt, split(t[rt].ls, val, x, t[rt].ls);
    else
        x = rt, split(t[rt].rs, val, t[rt].rs, y);
    pushup(rt);
}

Treap的分裂操作，用于维护凸壳。

核心DP过程

void dfs(int u, int l, int r) {
    // 递归处理子树
    run(ls[u], l, u);
    
    vec w(0, 0);
    for (int i = u;; i = rs[i]) {
        w = w + vec(1, a[i]);  // 构建当前链
        
        if (!rs[i] || a[i] != a[rs[i]]) {
            run(rs[i], i, r);  // 处理右兄弟
            break;
        } else
            run(ls[rs[i]], i, rs[i]);  // 处理右子树的左子树
    }
    
    // 合并子树信息，更新答案
    int r1, r2;
    Split(root[u], w, r1, r2);
    t[u] = {0, 0, (int)rnd(), w + t[r1].sum, w + t[r1].sum};
    root[u] = merge(u, r2);
    
    // 计算最终答案
    Split(root[u], w = vec(2, a[l] + a[r]), r1, r2);
    w = w + t[r1].sum, ans[u] = {w.y, w.x};
    root[u] = merge(r1, r2);
}

算法正确性

为什么使用笛卡尔树？

封闭序列 $A[i..j]$ 在笛卡尔树中对应一个子树：

• 根节点是序列的最小值（两端之一）
• 子树结构反映了序列的"山峰"形状
• 操作对应在树上选择一条路径

分数规划原理

我们在寻找最优子序列时，实际上是在解决：

$$\max \frac{\sum_{t \in S} A[t]}{|S|}$$

其中 $S$ 是包含端点 $i$ 和 $j$ 的子序列。

通过维护凸壳，我们可以高效找到斜率最大的线段。

复杂度分析

时间复杂度

• 初始化：$O(N \log N)$
  • 笛卡尔树构建：$O(N)$
  • DFS遍历：$O(N \log N)$（Treap操作）
• 单次查询：$O(1)$（答案已预计算）
• 总复杂度：$O(N \log N + Q)$

空间复杂度

• 笛卡尔树：$O(N)$
• Treap节点：$O(N)$
• 答案存储：$O(N)$
• 总空间：$O(N)$

算法优势

$1.$ 预处理优化：所有查询答案在初始化时预计算

$2.$ 数据结构结合：笛卡尔树反映序列结构，Treap维护凸壳

$3.$ 分数处理：直接处理分数比较，避免浮点误差

$4.$ 高效查询：$O(1)$ 时间回答每个查询

总结

本题通过将序列操作问题转化为笛卡尔树上的优化问题，结合Treap维护凸壳，实现了高效的预处理和查询。算法充分利用了封闭序列的结构特性和分数规划的数学性质，在 $O(N \log N + Q)$ 时间内解决了问题。

核心技巧：

• 笛卡尔树建模序列结构
• Treap维护分数凸壳
• 预处理所有可能查询
• 避免浮点运算的分数比较