Codeforces 946G Almost Increasing Array：删除位置与树状数组优化解析-北京尧图网络

1. 先搞清楚题目到底在问什么CodeForces 946G 这道 Almost Increasing Array我第一次做的时候栽在了一个很容易忽略的地方题目里的操作是“修改数组中元素的值”而 Almost Increasing 的定义是“存在一个位置删掉它之后剩余部分严格递增”。也就是说“删除”只是验证性质时的虚拟动作实际操作仍然是改数。想明白这一点后面的所有推导才走得通。题目的目标是最小化修改次数。设数组长度为 n最终数组要满足“删掉某个位置后严格递增”。那个被删掉的位置在验证时被排除所以它永远不需要被修改。真正需要考虑修改的只有剩下 n-1 个位置。因此最少修改次数可以写成n - 1 - 最多能保留多少个元素不改这里的“保留”指原始数组中的某些位置它们的值在最终数组里保持不变并且它们落在虚拟删除位置两侧后形成的序列严格递增。这个问题非常适合已经做过 Codeforces 那些经典“改成严格递增”题目的选手上手。它的内核是把严格递增这个条件通过下标偏移变成非下降再用最长不下降子序列的思路去解决。Almost 版本多加了一个自由度可以选择一个位置排除掉这会让下标偏移产生变化也就是后面反复出现的 b[i] 和 c[i]。一句话先给结论左侧的元素用 a[i] - i右侧的元素用 a[i] - (i - 1)中间可能需要跨过被删除的位置。这样处理后问题变成一个带一次跳转的最长不下降子序列问题用树状数组优化到 O(n log n) 就能通过 2e5 的数据。2. 严格递增怎么变成非下降2.1 整数数组特有的一条性质很多第一次接触这个模型的读者会疑惑为什么严格递增能等价于 a[i] - i 非下降考虑两个位置 i j如果原始数组最终序列是严格递增的那么 a[j] - a[i] 必须至少是 j - i因为数组元素都是整数相邻两个位置至少差 1隔了 d 个位置就至少要差 d。于是a[j] - a[i] j - i移项得到a[j] - j a[i] - i反过来如果对所有 i j 都有 a[j] - j a[i] - i那么 a[j] - a[i] j - i 0严格递增自然成立。所以“严格递增”这个看起来带不等号的约束在整数数组上完全可以写成“b[i] a[i] - i 是非下降的”。这就是经典最少修改次数问题的第一步转化。修改次数的最小值等于 n 减去 b 数组的最长不下降子序列长度。因为保留下来的元素必须满足 b 值非下降被修改的元素随便取什么值都可以它们不参与约束。这个结论在 Almost 版本中依然成立只是保留的元素可以绕开虚拟删除位置左右两侧的下标基准不同。2.2 虚拟删除位置带来的下标偏移现在假设我们选择最终验证时删除的位置是 k。那么剩余序列中原位置 i k 的元素它在剩余序列里的新下标还是 i所以保留条件需要满足 a[i] - i 非下降也就是用 b[i] a[i] - i。原位置 i k 的元素它在剩余序列里的新下标是 i - 1所以需要满足 a[i] - (i - 1) 非下降。令 c[i] a[i] - i 1。观察到一个很重要的关系c[i] b[i] 1也就是说被删除位置右侧的所有元素在数值上等价于把 b 值整体加 1。这个“加 1”来源于下标左移一格。题目所有的额外难度其实都集中在这个微小的偏移上。如果虚拟删除位置在数组末尾那么所有保留元素都在左侧全部用 b[i]这对应经典问题。如果虚拟删除位置在数组开头所有保留元素都在右侧全部用 c[i]。如果删除位置在中间那么保留序列由一段左侧 b 和一段右侧 c 拼起来中间需要跨过删除位置。注意因为元素值可以是任意整数所以被删除位置本身的原值是什么无所谓不管它满不满足递增关系都不需要我们修改。它被排除在验证之外。3. 动态规划的状态设计与转移3.1 两个状态分别管“删除前”和“删除后”直接枚举删除位置 k 再分别求 LNDS 会超时因为每次都是 O(n log n)总共 O(n^2 log n) 级别。需要把删除位置也融进 DP 过程里。设f[i]还没有确定虚拟删除位置并且当前保留序列以位置 i 结尾时最大保留数量。这个状态下位置 i 还在删除位置的左侧所以比较时使用 b[i]。g[i]已经确定了虚拟删除位置并且当前保留序列以位置 i 结尾时最大保留数量。这个状态下位置 i 在删除位置的右侧所以比较时使用 c[i]。注意“已经确定删除位置”并不需要真的在代码里记录删除发生在哪只需要知道当前路径已经跨过了删除位置。g 状态一旦进入后续所有元素都使用右侧的 c 值来比较。转移分三类第一类f[i] 从之前的 f 转移对应还在删除位置左侧f[i] max(f[j]) 1 j i 且 b[j] b[i]第二类g[i] 从之前的 g 转移说明删除位置在更早之前当前和之前的元素都在右侧g[i] max(g[j]) 1 j i 且 c[j] c[i]第三类g[i] 从某个 f[j] 跨跳而来说明保留序列前半段在左侧后半段从当前元素开始进入右侧中间恰好跨越虚拟删除位置g[i] max(f[j]) 1 j i - 1 且 b[j] c[i]第三类是整道题最容易写错的地方后面专门讲。另外删除位置在数组开头时左侧为空直接从“空状态”跳到右侧。这种情况下 g[i] 至少有 1相当于只保留当前元素这一个右侧元素。这个基线只在 i 2 时合法因为右侧第一个保留元素至少得是数组的第二个元素才能在前面留出一个位置供删除。3.2 为什么跨跳要求 j i - 1第三类转移是一个大坑。如果只写 j i那么当 j i - 1 时跨跳路径的前驱是 i - 1当前是 i中间没有任何元素可以去虚拟删除。所谓“删除位置在中间”就失效了这条路径实际上等于没有删除任何元素却混进了 g 状态。举一个具体反例n 2a [4, 5]。这个数组本身严格递增删除任意一个元素后剩下单个元素所以答案应该是 0 次修改。但如果允许 j i - 1 跨跳那么 f[1] 1g[2] f[1] 1 2保留数量变成 2算出来的答案是 2 - 1 - 2 -1显然错误。所以跨跳时必须保证 j 和 i 之间至少有一个空位用来充当被删除的位置。这就是 j i - 1 的来历。延迟更新就是解决这个约束的工程手段处理 i 时树状数组里只允许存放 f[1] 到 f[i-2]f[i-1] 必须等到下一轮才能加入。3.3 删除位置在末尾时f 要单独特判还有一个容易被忽视的情况虚拟删除位置在数组末尾。此时所有保留元素都在删除位置左侧整条保留链全部由 f 构成不会进入 g 状态。例如 n 3a [3, 1, 2]。删除末尾的 2剩下 [3, 1]不严格递增所以要改一个元素答案是 1。但如果删除中间剩下 [3, 2] 也要改一个所以答案同样是 1。这个例子里 g 链可能也能覆盖但更关键的是如果原始数组是 [1, 2, 3] 这样的严格递增数组删除末尾后剩下的 [1, 2] 不需要修改答案 0。此时最优方案完全由 f 路径给出。因此最后统计答案时不能只看 g 的最大值还要看 f[1] 到 f[n-1] 的最大值。注意是 f[n-1] 而不是 f[n]因为如果虚拟删除位置在末尾最后一个元素是被删除的那个它不能出现在保留链中。直接用 f[n] 会把不删除任何位置的方案也算进来导致答案变成负数。4. 树状数组优化与实现细节4.1 朴素 DP 的瓶颈与优化思路如果不优化转移需要枚举前面所有状态复杂度 O(n^2)2e5 的数据完全跑不动。观察转移条件f 转移要查 b[j] b[i] 的最大 f[j]。g 转移要查 c[j] c[i] 的最大 g[j]。跨跳转移要查 b[j] c[i] 的最大 f[j]。这些都是“值域上的前缀最大值查询”天然适合用 Fenwick 树维护。树状数组支持单点更新前缀最大值每次 O(log n)三棵树正好对应三类查询。之所以选 Fenwick 而不选线段树是因为需求只是前缀最大值没有区间修改树状数组代码短、常数小在 CF 这种对常数敏感的环境里体验很好。4.2 三棵树各司其职设三棵树bitA以 b[i] 为下标维护 f[i] 的最大值。供 f[i] 转移使用也供跨跳查询。bitB以 c[i] 为下标维护 g[i] 的最大值。供 g[i] 从 g 连续转移使用。bitC以 c[i] 为下标维护“可合法用于跨跳”的 f[i]。它比 bitA 慢一个周期更新确保跨跳只使用 f[i-2] 及更早的值。每次循环处理到 i 时用 bitA 查前缀最大值得到 f[i]。分别用 bitB 和 bitC 查前缀最大值加上 i 2 的基线 1得到 g[i]。用 f[i] 更新 bitA用 g[i] 更新 bitB。如果 i 2把 f[i-1] 加入 bitC。这一步实现了“延迟一个位置”。循环内的更新顺序至关重要。先算状态再更新树并且 bitC 的更新放到最后这样处理 i 时 bitC 里恰好只有 f[1] 到 f[i-2]跨跳约束自动满足。4.3 离散化细节b[i] a[i] - i 的范围大约是 [-2e5, 1e9]c[i] 只比 b[i] 大 1两者都需要参与离散化。把所有 b[i] 和 c[i] 收集到一个数组里排序去重然后用 lower_bound 映射到 1 开始的坐标。注意树状数组下标从 1 开始lower_bound 返回的索引要加 1。有一个常见错误只离散化 b 数组而不离散化 c 数组或者只离散化 c 而不离散化 b。因为三类查询分别会用到 b 和 c 的坐标所以两个集合必须都放进坐标池。4.4 完整代码#include bits/stdc.h using namespace std; struct Fenwick { int n; vectorint t; Fenwick(int n 0) { init(n); } void init(int n_) { n n_; t.assign(n 1, 0); } void update(int i, int v) { for (; i n; i i -i) t[i] max(t[i], v); } int query(int i) { int res 0; for (; i 0; i - i -i) res max(res, t[i]); return res; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorlong long a(n 1); for (int i 1; i n; i) cin a[i]; if (n 1) { cout 0 \n; return 0; } vectorlong long b(n 1), c(n 1), all; for (int i 1; i n; i) { b[i] a[i] - i; c[i] b[i] 1; all.push_back(b[i]); all.push_back(c[i]); } sort(all.begin(), all.end()); all.erase(unique(all.begin(), all.end()), all.end()); auto getId [](long long x) - int { return int(lower_bound(all.begin(), all.end(), x) - all.begin()) 1; }; int m all.size(); Fenwick bitA(m), bitB(m), bitC(m); vectorint f(n 1, 0), g(n 1, 0); int bestG 0; int bestFPrefix 0; for (int i 1; i n; i) { int bi getId(b[i]); int ci getId(c[i]); f[i] bitA.query(bi) 1; g[i] 0; if (i 2) g[i] 1; int qb bitB.query(ci); if (qb 0) g[i] max(g[i], qb 1); int qc bitC.query(ci); if (qc 0) g[i] max(g[i], qc 1); if (i n) bestFPrefix max(bestFPrefix, f[i]); bestG max(bestG, g[i]); bitA.update(bi, f[i]); if (g[i] 0) bitB.update(ci, g[i]); if (i 2) { int cp getId(c[i - 1]); bitC.update(cp, f[i - 1]); } } int bestKeep max(bestG, bestFPrefix); cout (n - 1) - bestKeep \n; return 0; }代码里 f 数组和 g 数组其实只用到最近一两个值理论上可以滚动但保留数组会让边界情况更清晰2e5 的空间开销完全可以接受。4.5 复杂度分析每个元素只会做常数次树状数组更新和查询每次 O(log n)。整体复杂度 O(n log n)空间 O(n)。n 最大 2e5这套代码实测跑下来不到 100ms在 CF 的时间限制内非常宽裕。5. 踩坑记录与一组手算样例5.1 三个容易错的地方第一个坑是 g 状态从“空”开始的基线。g[i] 只有在 i 2 时才能取到 1因为右侧第一个保留元素前面必须至少有一个元素可以充当虚拟删除位置。一开始我写成 g[i] 恒定为 1结果 n 1 的样例都能算错后来加特判才解决。第二个坑就是跨跳的延迟约束。最初实现时直接把 f[i] 全部放进同一个 bitA然后 g 的跨跳查询也查 bitA一测 n 2 的简单用例直接得到负数答案。问题出在 j i - 1 的非法跨跳。解决办法就是单独开一棵 bitC延迟一个周期更新。第三个坑是最后答案里的 f 前缀。严格递增的数组会触发 f[n] n如果不加限制直接用 max(f[n], bestG)答案会出现 -1。要牢记虚拟删除位置在末尾时第 n 个元素是被排除的那个不能出现在保留链中。所以答案里统计的 f 只能取到 f[n-1]。5.2 手算样例a [1, 5, 2, 3]这个例子非常能说明问题。答案是 0因为删除 5 之后剩下 [1, 2, 3]严格递增不需要修改。各步状态如下ib[i]c[i]f[i]g[i]说明10110没有可删除的位置23421f 保留 1 和 5g 只能从空开始3-1012g 通过 bitC 从 f1 跨跳删除位置 24-2-113g 通过 bitB 从 g3 连续转移第 4 行的 g[4] 3对应保留链a[1] 在左侧用 b删除位置 2a[3] 和 a[4] 在右侧用 c。检查一下a[1] - 1 0a[3] - 2 0a[4] - 3 0非下降序列 0, 0, 0 满足条件保留 3 个元素修改次数 4 - 1 - 3 0。这个样例也直观展示了“左侧 b、右侧 c、中间空一个位置”的完整路径。5.3 两个自测用例建议写完后至少跑这几组n 1输出 0。a [1, 2, 3]输出 0。a [1, 1, 1]输出 1。因为删除任意一个 1 后还剩下两个 1不严格递增必须把其中一个改成 2。a [5, 4, 3, 2, 1]输出多少答案是 3。严格递减数组删除一个元素后仍然整体递减至少要修改 3 个元素才能构造出几乎递增数组这能验证最终公式的兜底逻辑。我自己的习惯是先用朴素 O(n^2) DP 写一个对拍程序跑 n 10 的随机小数据验证优化版结果一致。这个小数据对拍几乎能命中所有边界问题比肉眼查代码高效得多。5.4 个人体会这题整体难度其实不在状态定义而在于把“虚拟删除位置”带来的下标偏移想清楚以及处理跨跳时那个微妙的位置差。我在实际调试中花最多时间的就是 j i - 1 这个约束如果一上来就看到延迟更新这个技巧会少走很多弯路。建议读者先自己写一版朴素 DP感受一下第三类转移的边界再回来对照树状数组的写法这样理解会扎实很多。

Codeforces 946G Almost Increasing Array：删除位置与树状数组优化解析

相关推荐

odbcji32.dll丢失修复指南：从SFC扫描到官方数据库驱动完整方案

【一人公司】2026 独立开发新范式：从 v0 到 Cursor，用 TaoToken 统一 Key 打通全链路 AI 提效

一天连开七个仓库对标 Adobe：本周 GitHub 上最猛的个人开发者是他

更多资讯

67K star 却只在日榜待了两小时：Docling 的热度含金量，到底有几分？

Android UI自动化测试：UI Automator与Espresso混合实战指南

Android Activity 功能代码实战：生命周期、状态保存与避坑指南

Java连接PostgreSQL完整指南：JDBC驱动、连接池与避坑清单

cua：命令行耗时分析器，追踪进程时间线上看不见的等待

Pytest项目接入Allure：从配置到CI集成的完整实战指南

今日更新

再见，SSE！你好，Streamable HTTP！轻松开发 Streamable HTTP MCP Server 并接入 TaoToken

工业软件标准化路线图：国产替代的落地施工图

VCMI安卓版实操指南：原生运行英雄无敌3的3步技术落地

本周精选

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？