F. Towering Arrays 详细题解

一、问题理解

给定数组 $a$，可以删除最多 $k$ 个元素。剩余数组 $b$ 称为 $p$-高塔数组，如果存在一个中心下标 $i$，使得对于所有位置 $j$：

$$b_j \ge p - |i - j|$$

等价地，如果以 $i$ 为中心，从中心向两侧的值必须至少呈线性递减（斜率 $-1$），且不能低于 $p - dist$。

目标：找到最大的 $p$ 使得存在一种删除方式（删 $\le k$ 个元素）后数组成为 $p$-高塔数组。

---

二、核心转化

固定 $p$，问题变为：判断能否通过删除 $\le k$ 个元素，使得剩余数组满足 $p$-高塔条件。

等价描述：存在一个中心下标 $i$（在剩余数组中的位置），使得对于所有剩余位置 $j$：

$$a_j \ge p - |i - j|$$

注意 $i$ 是剩余数组中的下标，不是原数组下标。但我们可以将问题映射回原数组：在原数组中选择一个子序列（保持顺序），使其成为 $p$-高塔数组。

---

三、关键观察

对于固定的 $p$，定义每个位置 $j$ 的 需求值：

$$need_j = p - |i - j|$$

但 $i$ 未知。换个角度：如果我们知道中心在原数组中的位置 $i$，那么所有满足 $a_j \ge p - |i - j|$ 的位置 $j$ 都可以保留，其余需要删除。

但中心 $i$ 本身必须在剩余数组中（即 $a_i \ge p$，因为 $|i-i|=0$）。

---

四、单调性与二分答案

答案 $p$ 具有单调性：如果 $p$ 可行，则更小的 $p$ 也可行（因为需求降低）。因此可以二分答案。

对于给定的 $p$，需要判断是否存在一个中心位置，使得需要删除的元素数 $\le k$。

---

五、判定算法

固定 $p$，定义：

• 对于每个位置 $i$，如果 $a_i \ge p$，它可能成为中心。
• 对于每个位置 $j$，如果 $a_j \ge p - |i - j|$，则它可以保留。

但直接枚举中心 $i$ 会 $O(n^2)$，不可行。

关键技巧：将条件拆分为左右两部分。

1. 前缀处理

定义 $pref[i]$ 表示：如果中心在 $i$ 或右侧，前 $i$ 个位置（包括 $i$）中能保留的最大数量。

更常用的是标程中的方法：

标程通过一个过程 $f(n, p, res)$ 计算数组 $res$，其中 $res[i]$ 表示：以 $i$ 作为最后一个保留的元素时，最多能保留多少个元素（且这些元素满足 $p$-高塔条件，中心在保留序列的最右端？需要仔细理解）。

实际上，标程的 $f$ 函数模拟了以下过程：

从左到右扫描，维护一个数据结构，对于每个位置 $i$，计算以 $i$ 为结尾的最长合法子序列的长度（该子序列以某个点为中心，中心可能在左边或右边）。但标程的处理是对称的。

2. 标程的 $f$ 函数解析

void f(int n, int p, int *res) {
    Segtree tree(n);
    int cur_sz = 0;
    for (int i = 0; i < n; i++) {
        tree.update(i, p - a[i]);
        int pos = i;
        while ((pos = tree.find_prev_non_pos_put_inf(pos)) != -1) {
            cur_sz++;
            tree.add_on_segment(0, pos, -1);
        }
        res[i] = cur_sz;
    }
}

• 线段树维护每个位置的 p - a[i] 值（即需要额外补偿的值）
• find_prev_non_pos_put_inf(pos) 找到 $[0, pos]$ 中第一个 $\le 0$ 的位置，并将其设置为 $+\infty$（表示已使用）
• 每次找到这样一个位置，cur_sz 增加，并将 $[0, pos]$ 区间整体减 $1$（因为多保留一个元素，后续位置的需求降低？）

这个过程的含义是：贪心地从右到左选取尽可能多的位置，使得它们满足递减条件。最终 $res[i]$ 表示前 $i+1$ 个位置中最多能选出的元素个数，这些元素可以构成一个以最右侧为峰值的“山峰”形状。

3. 对称处理

标程分别计算：

• pref[i]：从左到右，以 $i$ 为结尾的最长合法前缀序列长度
• suf[i]：从右到左，以 $i$ 为开头的最长合法后缀序列长度

然后对于每个可能成为中心的位置 $i$（要求 $a_i \ge p$），总保留数 = pref[i] + suf[i] - 1（因为 $i$ 被算了两次）。

如果存在某个 $i$ 使得 $n - (pref[i] + suf[i] - 1) \le k$，则 $p$ 可行。

---

六、二分边界

• 下界 $l = 0$（$p$ 至少为 $0$）
• 上界 $r = \max(a) + 1$（因为 $p$ 不会超过最大 $a_i + n$，但这里取 $\max(a)+1$ 即可）

---

七、算法流程总结

1. 二分答案 $p$
2. 对于给定的 $p$：
   • 调用 f(n, p, pref) 计算前缀最长保留长度
   • 反转数组，再调用 f 计算后缀最长保留长度（得到 suf）
   • 反转 suf 使其下标对应原数组
   • 遍历所有 $i$ 满足 $a_i \ge p$，计算 $mx = \max(pref[i] + suf[i] - 1)$
   • 如果 $n - mx \le k$，则 $p$ 可行
3. 输出最大的可行 $p$

---

八、复杂度分析

• 二分：$O(\log \max a) \approx O(30)$
• 每次判定：$O(n \log n)$（线段树操作）
• 总复杂度：$O(n \log n \log \max a)$，满足 $n \le 2\times 10^5$

---

九、示例验证

以第一个测试用例为例：

n=5, k=0, a=[2,1,4,5,2]

二分 $p=3$：

• 计算得 $pref = [1,1,2,3,3]$，$suf = [1,1,2,3,2]$
• 对于 $i=3$（$a_3=4 \ge 3$），$pref[3]+suf[3]-1 = 3+3-1=5$
• $n - 5 = 0 \le k$，可行
• $p=4$ 不可行，最终答案 $3$

---

十、总结

要点	说明
核心思想	二分答案 + 贪心线段树判定
判定方法	计算每个位置作为结尾/开头的最长合法序列长度
数据结构	线段树维护最小值，支持区间加和单点赋值
时间复杂度	$O(n \log n \log \max a)$
空间复杂度	$O(n)$