企业官网建设流程全解析

第一次做 CodeForces 946G 的时候，我第一反应是“这不就是 LIS 加个特判吗”，结果交上去 WA 到怀疑人生。后来自己手动算了一组数据才发现，这道题最阴险的地方根本不在二分求 LIS，而在“删除一个元素之后，整个数组的下标会整体左移”这件事上。下标一变，严格递增的判断条件就全变了，所有直觉上的贪心都会在这里翻车。

如果你正准备刷 Almost Increasing Array，或者已经把题读了一遍但没想明白到底要维护什么，这篇题解应该能帮你把整个推导串起来。我会从题意重新翻译开始，讲清楚为什么要构造 b[i] = a[i] - i，再给出一份 O(n log n) 的完整做法，最后把几个容易写挂的细节单独拎出来说。

1. 先重新翻译一下题意：到底在求什么

题目说的是：给你一个长度为 n 的数组 a，你最多可以删除一个元素，也可以对任意元素改成任意整数值，目标是让剩下的数组变成严格递增。问最少操作多少次。

注意这里“操作”包含两件事：删除一次算一次操作，修改一个元素也算一次操作。所以如果你选择删除一个位置，那么你花的代价就是：

• 1 次删除操作；
• 对剩下 n-1 个元素中所有不满足条件的位置做修改。

换句话说，我们真正想要的其实是：在最多删一个元素的前提下，最多能保留多少个元素不动。保留得越多，需要修改的就越少。设最大保留数为 keep，答案就是 n - keep。这个统一公式在“删和不删”两种情况下都成立：

• 不删除时，修改次数 = n - keep；
• 删除时，删除 1 次 + 修改 (n-1-keep) 次 = n - keep。

所以核心问题只有一个：计算最大保留数 keep。

很多人一开始会把这个问题拆成“枚举删哪个位置，然后求两边 LIS”，但直接这么想会漏掉一个关键点：删除位置右侧的所有元素，它们的下标不是原来那个下标了。右侧第一个保留元素在原数组里是第 r 个，删除后它变成第 r-1 个，它的判定条件自然也要跟着变。这就是我开头说的“下标位移”。

2. 最关键的一步：严格递增为什么要变成非递减

先看不删除的情况。假设我们最终保留了一堆原位置上的元素，其中两个保留位置是 i < j，那么最终数组里它们必须满足：

a[i] < a[j]

但仅仅这样不够，因为 i 和 j 之间还可能插入一些被修改的元素。这些被修改的元素可以填任意整数值，只要整体严格递增。如果 a[j] - a[i] 不够大，中间插不下足够多的不同整数，构造就会失败。

比如 i=2, j=4，中间只有一个空位，要想在两个保留元素之间塞进一个严格递增的整数 x，必须满足 a[i] < x < a[j]，x 是整数，至少需要 a[j] - a[i] ≥ 2。更一般地，如果 i 和 j 之间有 d 个空位，就需要：

a[j] - a[i] ≥ d + 1

而 d + 1 = j - i。所以条件等价于：

a[j] - a[i] ≥ j - i

移项得到：

a[i] - i ≤ a[j] - j

这时候自然引入：

b[i] = a[i] - i

两个能同时保留的原位置，必须满足 b[i] ≤ b[j]。也就是说，保留的原位置集合在 b 数组上必须是一个非递减子序列。于是“最少修改多少使数组严格递增”就变成了“b 数组的最长非递减子序列长度”。这就是整道题最重要的一个转换。

这里要注意是“非递减”，不是“严格递增”。因为 a 是严格递增，减掉下标之后 b 是非递减。如果用 lower_bound 做 LIS，会把相等的 b 值当成不能保留，结果会小一截。必须用 upper_bound。

3. 删除一个元素以后，公式变成了 f[i] + g[j]

现在考虑最多删除一个元素。假设删除位置是 p，那么原数组里下标小于 p 的部分保持不变，下标大于 p 的部分全部左移一位。对右侧任意一个原下标 x，它在新数组里的位置是 x-1，所以它对应的判定值变成：

a[x] - (x-1) = a[x] - x + 1 = b[x] + 1

也就是说，右半段的每个元素整体加了一个常数 1。整体加常数不会改变右半段内部的相对大小关系，所以右半段内部仍然等价于找 b 的非递减子序列。但左右两段拼接的时候，左侧最后一个保留元素的值是 b 形式，右侧第一个保留元素的值是 b+1 形式，两者之间多了一个“放宽一格”的机会。

我们定义两个 DP 数组：

• f[i]：在 b[1..i] 中，以 i 结尾的最长非递减子序列长度；
• g[j]：在 b[j..n] 中，以 j 开头的最长非递减子序列长度。

如果删除点 p 夹在左右两段之间，设左侧最后保留元素为 i，右侧第一个保留元素为 j，那么必须满足：

i < p < j

这个条件意味着 i 和 j 中间至少要隔一个元素可以删，也就是 j ≥ i+2。

两段合起来能保留的元素数是 f[i] + g[j]。拼接条件除了位置上的要求，还有值上的要求：

b[i] ≤ b[j] + 1

右侧整体偏移了 1，所以左侧最后一个元素只要不大于右侧第一个元素的 b[j]+1 就能接上。

于是，删除一个元素时，最大保留数就是所有满足 i+1 < j 且 b[i] ≤ b[j]+1 的 f[i] + g[j] 的最大值。把所有保留元素都放在同一侧的情况不需要单独处理，因为不管是全放左侧还是全放右侧，它本质上都是 b 数组的一个非递减子序列，长度不可能超过全局 LNDS，所以最后跟全局 LNDS 取 max 就能兜住。

最终答案就是：

ans = n - max(LNDS, max_{j ≥ i+2, b[i] ≤ b[j]+1} (f[i] + g[j]))

4. 三个 DP 怎么算：前缀、后缀、合并枚举

4.1 前缀 f[i]：经典 nlogn LNDS

f[i] 直接用 dp 数组加二分。因为要的是非递减，所以用 upper_bound 找到第一个严格大于 b[i] 的位置，然后替换或者追加。

vector<int> f(n + 1); vector<long long> dp; for (int i = 1; i <= n; i++) { int pos = int(upper_bound(dp.begin(), dp.end(), b[i]) - dp.begin()); if (pos == (int)dp.size()) dp.push_back(b[i]); else dp[pos] = b[i]; f[i] = pos + 1; } int lnds = (int)dp.size();

dp.size() 就是全局 LNDS，也就是不删除时的最大保留数。

4.2 后缀 g[i]：倒着扫加值域 BIT

g[i] 的定义是从 i 出发到 n 的最长非递减子序列长度，需要查询后面是否存在值不小于 b[i] 的元素。从右往左扫，配合一个按值域维护最大值的数据结构。

因为要查询的是“值不小于某个数”，取反下标把它变成前缀查询比较方便：

vector<int> g(n + 1); BIT bitR(m); for (int i = n; i >= 1; i--) { int pos = getId(b[i]); int rev = m - pos + 1; // 把后缀查询翻成前缀查询 g[i] = bitR.qry(rev) + 1; bitR.upd(rev, g[i]); }

m 是离散化后的值域大小。这里需要把 b[i] 和 b[i]+1 一起放进离散化数组，因为后面查询 b[j]+1 时要用。

4.3 合并答案：延迟插入的 BIT

求 max(f[i] + g[j]) 最自然的想法是枚举 j，然后在已枚举过的 i 里找满足 b[i] ≤ b[j]+1 的最大 f[i]。但这里有一个特别容易写错的点：i 和 j 之间必须夹着一个可删除的位置，也就是 i ≤ j-2。如果直接把 1..j-1 的 f[i] 全部插进 BIT，会把 i = j-1 这种中间没有空位的组合也算进去，这种组合实际是删不出一个合法位置的。

所以需要延迟插入。枚举 j 的时候，只把 i = j-2 这个新位置插进去，这样 BIT 里保留的永远是 i ≤ j-2 的信息。

BIT bitF(m); int best = lnds; for (int j = 3; j <= n; j++) { int i = j - 2; int pos = getId(b[i]); bitF.upd(pos, f[i]); int lim = int(upper_bound(vals.begin(), vals.end(), b[j] + 1) - vals.begin()); int leftMax = lim ? bitF.qry(lim) : 0; best = max(best, leftMax + g[j]); }

这里的 lim 是离散化数组里小于等于 b[j]+1 的元素个数，也就是 BIT 里允许查询的前缀范围。leftMax 是满足值条件的最大 f[i]，g[j] 是以 j 开头的后缀最优值。

循环从 j=3 开始是因为至少要有 i=1 才能在 j=3 时满足 i ≤ j-2。j 太小时不存在合法的左右组合，但那些情况已经被 lnds 兜住了。

5. 完整代码与复杂度分析

整理一下，完整 C++17 实现如下：

#include <bits/stdc++.h> using namespace std; struct BIT { int n; vector<int> t; BIT(int n) : n(n), t(n + 2, 0) {} void upd(int x, int v) { for (; x <= n; x += x & -x) t[x] = max(t[x], v); } int qry(int x) { int res = 0; for (; x > 0; x -= x & -x) res = max(res, t[x]); return res; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<long long> a(n + 1), b(n + 1); vector<long long> vals; for (int i = 1; i <= n; i++) { cin >> a[i]; b[i] = a[i] - i; vals.push_back(b[i]); vals.push_back(b[i] + 1); } sort(vals.begin(), vals.end()); vals.erase(unique(vals.begin(), vals.end()), vals.end()); int m = (int)vals.size(); auto getId = [&](long long x) { return int(lower_bound(vals.begin(), vals.end(), x) - vals.begin()) + 1; }; // 前缀 f[i]：以 i 结尾的 LNDS vector<int> f(n + 1); vector<long long> dp; for (int i = 1; i <= n; i++) { int pos = int(upper_bound(dp.begin(), dp.end(), b[i]) - dp.begin()); if (pos == (int)dp.size()) dp.push_back(b[i]); else dp[pos] = b[i]; f[i] = pos + 1; } int lnds = (int)dp.size(); // 后缀 g[i]：以 i 开头的 LNDS vector<int> g(n + 1); BIT bitR(m); for (int i = n; i >= 1; i--) { int pos = getId(b[i]); int rev = m - pos + 1; g[i] = bitR.qry(rev) + 1; bitR.upd(rev, g[i]); } // 枚举右端点 j，延迟插入左端点 i=j-2 BIT bitF(m); int best = lnds; for (int j = 3; j <= n; j++) { int i = j - 2; int pos = getId(b[i]); bitF.upd(pos, f[i]); int lim = int(upper_bound(vals.begin(), vals.end(), b[j] + 1) - vals.begin()); int leftMax = lim ? bitF.qry(lim) : 0; best = max(best, leftMax + g[j]); } cout << n - best << '\n'; return 0; }

复杂度很清晰：离散化 O(n log n)，两个 BIT 每个元素一次更新一次查询 O(n log n)，二分求 LNDS 也是 O(n log n)，总复杂度 O(n log n)，空间 O(n)。n 到 2e5 的规模完全没压力。

6. 这里有几个我踩过的坑，建议直接避开

6.1 upper_bound 和 lower_bound 千万别用混

b 数组要的是最长非递减子序列，所以二分必须用 upper_bound。如果这里用了 lower_bound，遇到 b[i] 相等的情况也会被当成要替换的位置，保留长度立刻变短。很多题目里求严格递增 LIS 用 lower_bound，求非递减用 upper_bound，这个对应关系一定要背牢。

6.2 右侧的偏移是 +1，不是 -1

删除一个元素后，右侧原下标 x 变成 x-1，所以 b[x] = a[x]-x 变成了 a[x]-(x-1) = b[x]+1。我第一次推导的时候把符号写反了，结果合并条件变成了 b[i] ≤ b[j]-1，整个答案错得很隐蔽，小样例能过，大样例直接挂。记住：下标变小，减去的数变小，整体值变大。

6.3 合并时一定要延迟插入

枚举 j 时如果在插入 f[j-1] 之后再查询，会把 i=j-1 的组合算进去。但 i 和 j 之间没有可删除的位置，这种组合根本不可能通过删除一个元素实现。为什么很多题解强调 j 从 3 开始、插入 i=j-2，就是为了保证中间永远夹着至少一个元素。

6.4 b[j]+1 必须进离散化

BIT 是按离散化值域开的，查询条件是 b[i] ≤ b[j]+1。如果离散化数组里只放了 b[i]，upper_bound 查 b[j]+1 结果可能落在错误的位置。把所有需要的值和查询值一起离散化是最稳妥的，省得边界判断写半天。

6.5 答案不要只算删除的情况

如果数组本身就严格递增，答案是 0。这时候最优策略是“不删除”，但你枚举删除点得到的保留数反而可能小于 n。开头写的 best 初始值就是 lnds，也就是强制把“不删除”的选项包含进去。这个初始化千万不要顺手写成 0。

7. 这个套路还能往外扩一步

Almost Increasing Array 的核心套路其实可以抽象成一句话：当序列允许删除一个元素时，后半段的“判定基准”整体偏移了一个单位，于是需要把左右两段按照偏移后的条件重新拼起来。这个思路在很多“最多删 k 个元素”的题目里都能用，只是转移状态从一维变成二维，BIT 维护的维度也会变多。

如果以后遇到类似的“删除后递增/递减”问题，可以优先想想：

• 删除后右侧元素的下标变化是多少，判定条件怎么变；
• 左侧和右侧各自的子问题是否还是标准 LIS；
• 左右拼接时中间是否必须夹着可删除的空位。

把这三个问题想清楚，这类题基本就不会跑偏了。我自己实际写这题的时候，最大的感受是：算法本身不难，难的是把“下标位移”翻译成公式之后还能记得在代码里体现出来。延迟插入那一步我至少错了两回才彻底记住原因，希望你一次就做对。