今天刷题计划到了第2971题碰上了这道 [CEOI 2018] Global warming。初看题目名以为又是那种套个壳的LIS模板题结果仔细一读发现它有一个非常有意思的操作我可以选一个连续区间把这个区间里的所有数同时减去一个非负整数 x然后问整个数组的最长严格上升子序列能有多长。这个整体减 x的动作直接把普通 LIS 的解法打乱了因为你没法简单地用前驱数组、后继数组把它们拼起来——值域上的约束被一个统一的偏移量搅在了一起。我从拿到题到完全推导出 O(n log n) 的做法中间绕了不少弯路最后发现一个特别关键的观察任何最优解都可以等价地看成只把数组前缀整体压低或者只把数组后缀整体压低。一旦接受了这个设定这道题就从枚举区间两端变成了枚举切分点难度直接下降了一个维度。这篇文章就把完整的思考过程、正确性证明、实现代码和踩坑细节都记录下来希望能给同样在刷信奥题的朋友省点时间。1. 题目到底在说什么一个区间同时降温LIS 会变成什么样先把题意理解透。给定长度为 n 的数组 a我可以选择任意一个连续区间 [l, r]也可以不选相当于 x0再选择一个非负整数 x然后把区间内的每个元素都减去 x。做完这一步操作后在整个数组上求最长严格上升子序列的长度目标是让这个长度尽量大输出最大值。需要注意的是区间内部的所有元素是同步降温的它们之间的相对大小关系一点都不会变。原来 a[i] a[j]i、j 都在区间内操作后依然有 a[i]-x a[j]-x。所以这个操作的真正威力不体现在区间内部而是体现在区间边界的连接上它可以让区间里的元素相对于区间左边的元素变小同时相对于区间右边的元素也变小——但这两件事是有冲突的x 太大区间内元素就很难再接上右边的数x 太小又可能接不上左边的数。这种两边都想接但 x 只有一个的矛盾正是这道题的核心难点。如果直接把操作区间当成一个整体去枚举左右端点复杂度根本压不下去。我当时第一反应是能不能像普通 LIS 那样预处理出以某个位置结尾的最长上升子序列长度和以某个位置开头的最长上升子序列长度然后枚举操作区间覆盖的位置合并两边答案。结果试了一下就发现不行因为跨过区间的比较会依赖 x前缀选的子序列和后缀选的子序列不是简单相加就能成立的关系。后来我换了个角度问自己既然 x 可以取得非常大那我干脆把整个前缀都压到特别低让前缀和后面的所有数都能接上岂不是更自由这个想法一开始我自己都不太敢信因为把更多元素也减 x似乎会破坏前缀内部原来的上升关系。但仔细一想前缀内部是同时减同一个 x相对顺序完全保留所以破坏不了。沿着这个方向继续推就得到了整道题最关键的性质。2. 关键突破口任意操作区间都可以等价地变成前缀操作或后缀操作这里先说结论对于任意一个最优的操作区间 [l, r] 和减量 x我总可以把操作区间扩展成前缀 [1, r]或者扩展成后缀 [l, n]而最终的最长上升子序列长度不会减少。也就是说我只需要考虑把一段前缀整体压得很低或把一段后缀整体压得很低这两种情况就够了。为什么能这样扩展假设我已经有了一个最优操作区间 [l, r]以及在这个操作下取到的最优上升子序列 S。现在我把操作区间变成 [1, r]也就是把原来不动的前半段 1 到 l-1 也一并减去同一个 x。我需要检查 S 是否仍然是一个合法的上升子序列。如果 S 中的两个相邻元素原来都在 [1, l-1] 里那么它们现在都被减 x差值不变依然上升。如果两个相邻元素原来分别在 [1, l-1] 和 [l, r] 里那么它们现在都被减 x依然维持原来的大小关系。如果两个相邻元素原来分别在 [l, r] 和 [r1, n] 里这是原始最优解里已经成立的关系现在也不受影响。最难的是两个相邻元素原来分别在 [1, l-1] 和 [r1, n] 里也就是跨越了原来整个操作区间。在原始的最优解 S 中这两个元素之间必然还隔着至少一个 [l, r] 内的元素因为 S 是一个连续的上升序列不可能直接从前面跳到后面中间不经过任何区间内元素所以它们之间的大小关系其实是间接通过区间内元素传导的。现在区间内元素被减 x变得更小了最后落到 [1, l-1] 里的元素也被减 x变得更小了所以这个跨段比较不仅没被破坏反而更加宽松。因此S 在扩展成前缀操作后依然是一个合法的上升子序列长度不变。这就说明只要某个中间区间能取到最优解那么把它扩展成前缀或者后缀同样能取到至少这么长的解。于是问题规模一下子从任意区间缩小到了一个切分点。有了这个观察之后还有一个隐藏的简化x 可以取得足够大。因为前缀操作只有一边需要对接前缀里最后一个被选中的元素减 x 之后可以变得要多小有多小后缀里的第一个元素只要比它大就行这个要求毫无压力。所以对于前缀 [1, r]我根本不用关心前缀选的上升子序列具体末尾值是多少只要它是前缀里最长的上升子序列就行。前缀内部的所有元素同时减 x内部关系不变所以前缀 [1, r] 里最长能选多长这个问题就是原数组在 [1, r] 内的普通最长上升子序列长度。同样的道理后缀操作 [l, n] 对应的是前缀 [1, l-1] 的最长上升子序列长度加上后缀 [l, n] 的最长上升子序列长度。到这里这道题就变成了一个完全不同的、干净得多的问题枚举一个切分点 r把数组切成长度可变的前缀 [1, r] 和后缀 [r1, n]分别求出这两个部分各自的最长严格上升子序列长度加起来取最大值。这就是整个解法的骨架。3. 答案公式为什么前缀最长 LIS 和后缀最长 LIS 可以直接1 拼起来有些人看到这里可能会觉得不对劲普通 LIS 里如果把数组切成两半分别求出左边的最长上升子序列和右边的最长上升子序列是不能直接相加的因为左边子序列的最后一个值可能大于右边子序列的第一个值拼接不起来。但在这个题里这个限制恰好被操作消掉了。我们具体看一下。设切分点为 r前缀 [1, r] 被整体减去一个很大的 x。选中前缀里的一个上升子序列 A它内部严格上升选中后缀 [r1, n] 里的一个上升子序列 B它内部也严格上升。现在只需要验证 A 的最后一个元素能不能接上 B 的第一个元素。因为 A 是上升序列A 的最后一个元素就是 A 中的最大值记它原来为 a_ii ≤ r。B 是上升序列B 的第一个元素就是 B 中的最小值记它原来为 a_jj r。操作后a_i 变成了 a_i - x。只要我选的 x 足够大使得 a_i - x a_j那么 A 中所有元素都小于 a_jB 中所有元素又都从 a_j 开始递增整条 A B 就严格上升了。这种 x 存在吗当然存在整数范围内取 x max(0, a_i - a_j 1) 就行。这个x 可以足够大的性质等于让我放弃了跨切分点的值域约束。剩下的唯一约束就是位置约束前缀里的位置一定在后缀位置之前这是切分点天然保证的。所以前缀部分能取到的最长上升子序列长度和后缀部分能取到的最长上升子序列长度直接相加就是当前切分点能得到的答案完全不需要管具体的末尾值。注意这里有一个细节前缀整体减 x 之后前缀里那些没有被选进 A 的元素会不会影响 B不会。因为最长上升子序列只看我选出来的那一个子序列其他元素是无所谓的它们再小也不会干扰已经选好的序列。另外一个细节是 x 可以等于 0所以如果原数组的普通 LIS 本身就很大它也会被这个公式覆盖到不需要特判。于是最终答案公式写出来非常简洁ans max( 0 ≤ r ≤ n 的 preMax[r] sufMax[r1] )其中 preMax[r] 表示原数组前缀 [1, r] 内最长严格上升子序列的长度sufMax[s] 表示原数组后缀 [s, n] 内最长严格上升子序列的长度。空前缀或空后缀的长度记为 0。这个公式把前后缀操作的情况都包含了。当你想到 r 时既可以理解为把 [1, r] 压扁再接上右边也可以理解为把 [r1, n] 压扁接到左边原来已经选好的序列后面两者是同一个枚举。普通 LIS 的情况被 r0 和 rn 覆盖r0 就是整个数组作为后缀长度为普通 LISrn 就是整个数组作为前缀长度也是普通 LIS。所以这个 ans 至少不会小于原数组的 LIS。验证一个具体例子会很有感觉。比如数组 [5, 1, 3, 2, 4]普通 LIS 长度是 31,3,4 或者 1,2,4。用公式枚举切分点 r1前缀 [5] 的 LIS 长度是 1后缀 [1,3,2,4] 的 LIS 长度是 3加起来是 4。这个解对应实际操作是把前缀 [5] 整体减去 5得到 [0,1,3,2,4]最长上升子序列可以选 0,1,2,4长度正好是 4。这说明公式不仅算出来了而且给出的操作方式也是直观可行的。4. 工程实现树状数组双向扫描加切分点枚举公式已经非常干净剩下的就是怎么快速求每个前缀和后缀的最长严格上升子序列长度了。这部分我用树状数组做复杂度 O(n log n)完全能扛住 n 2e5 级别的数据。先正向扫描一遍维护 preLIS[i] 表示以第 i 个元素结尾的最长严格上升子序列长度。这个就是经典 LIS 的树状数组写法把数组值离散化成 1 到 m 的排名用树状数组维护以某个排名为结尾的最长上升子序列长度每次查询小于当前排名位置上的最大值加 1 后更新到当前排名上。因为要求严格上升查询的是当前排名之前的最大值也就是 lower_bound 得到的排名减一。再反向扫描一遍维护 sufLIS[i] 表示以第 i 个元素开始的最长严格上升子序列长度。正向扫描是找前面比它小的元素反向扫描就是找后面比它大的元素。树状数组默认方便做前缀查询反过来做后缀查询时我会把排名反转一下把离散化后最大的排名变成 1最小的变成 m这样找后面比它大的元素就变成了在新排名下找比它小的元素就可以继续用同一个树状数组模板了。这是实现里最容易写错的地方我会在代码里单独注释出来。拿到 preLIS 和 sufLIS 之后还需要两个辅助数组 preMax 和 sufMax。preMax[r] 是 preLIS[1] 到 preLIS[r] 的前缀最大值也就是前缀 [1, r] 的整体 LIS 长度sufMax[s] 是 sufLIS[s] 到 sufLIS[n] 的后缀最大值也就是后缀 [s, n] 的整体 LIS 长度。这两个数组用一遍递推就能得到。最后枚举切分点 r0 到 n对所有 preMax[r] sufMax[r1] 取最大值。完整 C17 实现如下。代码里值域全部用 long long 读入防止题目给到 1e9 级别的数时和内部临时计算冲突树状数组维护的是长度用 int 就够了。#include bits/stdc.h using namespace std; const int N 200005; int n; long long a[N]; vectorlong long vals; int preLIS[N], sufLIS[N]; int preMax[N], sufMax[N]; struct BIT { int n; vectorint c; BIT(int n) : n(n), c(n 1, 0) {} void update(int i, int v) { for (; i n; i i -i) { c[i] max(c[i], v); } } int query(int i) { int res 0; for (; i 0; i - i -i) { res max(res, c[i]); } return res; } }; int main() { scanf(%d, n); for (int i 1; i n; i) { scanf(%lld, a[i]); vals.push_back(a[i]); } // 离散化rank 从 1 开始值越大 rank 越大 sort(vals.begin(), vals.end()); vals.erase(unique(vals.begin(), vals.end()), vals.end()); int m (int)vals.size(); vectorint rank(n 1); for (int i 1; i n; i) { rank[i] int(lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin()) 1; } // 正向扫描以 a[i] 结尾的最长严格上升子序列长度 BIT bitForward(m); for (int i 1; i n; i) { preLIS[i] bitForward.query(rank[i] - 1) 1; bitForward.update(rank[i], preLIS[i]); } preMax[0] 0; for (int i 1; i n; i) { preMax[i] max(preMax[i - 1], preLIS[i]); } // 反向扫描以 a[i] 开头的最长严格上升子序列长度 // 将排名反转使得“原排名更大”对应“新排名更小” vectorint revRank(n 1); for (int i 1; i n; i) { revRank[i] m - rank[i] 1; } BIT bitBackward(m); for (int i n; i 1; --i) { // 找原排名比 rank[i] 大的即新排名比 revRank[i] 小的 sufLIS[i] bitBackward.query(revRank[i] - 1) 1; bitBackward.update(revRank[i], sufLIS[i]); } sufMax[n 1] 0; for (int i n; i 1; --i) { sufMax[i] max(sufMax[i 1], sufLIS[i]); } int ans 0; for (int r 0; r n; r) { ans max(ans, preMax[r] sufMax[r 1]); } printf(%d\n, ans); return 0; }代码整体结构很清楚预处理离散化排名正反两遍树状数组两个辅助数组一个循环枚举答案。这个解法的时间复杂度和空间复杂度都是 O(n log n) 和 O(n)对 n2e5 的极限数据来说跑起来非常轻松基本在一毫秒级别的量级。这里说一下树状数组求 LIS 的一个实现习惯。树状数组的 update 是取 max 而不是累加query 也是取前缀 max。这跟普通用树状数组求逆序对不一样刚切换时容易手滑写成累加。另一种常见写法是离散化后每次 update(k, 1)然后 query 总和但那种写法只能用于判断是否存在长度场景下还是要维护 max。我习惯把 BIT 的 update 和 query 写成 max 版本因为这个模板在 LIS 相关题目里复用率极高。5. 边界情况和易错点这些坑我实际调试时都踩过边界情况是最容易丢分的部分。我罗列一下这个题里常见的几个坑如果你自己写的时候 WA 了几发多半就是下面某一类问题。第一个坑是后缀 LIS 的方向没搞清楚。正向 LIS 大家都很熟以 i 结尾看前面小于 a[i] 的元素。反向 LIS 是以 i 开头看后面大于 a[i] 的元素。如果不做排名反转直接拿原排名去树状数组里 query会算出以 i 开头的最长不下降子序列之类的东西完全不是目标。这个反转映射建议单独写一个 revRank 数组不要在原 rank 上直接修改否则调试的时候很难看清。第二个坑是树状数组的查询位置。严格上升要求两侧比较必须严格小于或严格大于。正向时 query(rank[i]-1)因为等于 rank[i] 的值不算反向时 query(revRank[i]-1)因为等于原排名的值要排除。如果你把减一漏掉遇到大量重复元素就会得出错误答案。举一个极端例子[2, 2, 2]严格上升 LIS 长度是 1但如果不排除相等值算出来会变成 3。第三个坑是切分点枚举的边界。切分点 r 可以从 0 取到 nr0 表示前缀为空、整个数组都作为后缀rn 表示后缀为空、整个数组都作为前缀。如果循环写成 1 到 n-1就会漏掉完全不操作和整体操作一个前缀的情况导致答案偏小。辅助数组 preMax[0]0 和 sufMax[n1]0 不能忘记初始化因为空部分的 LIS 长度显然是 0。第四个坑是重复值带来的严格上升问题。题目要求的是严格上升也就是说 a[i] a[j]而不是 a[i] ≤ a[j]。离散化去重之后相等值共享同一个排名这正好帮助我们排除相等值参与上升序列。如果你离散化时没有去重或者排序后没有 uniquerank 会分成不同的编号相等值就会被错误地当作可以连续选择得到偏大的答案。第五个坑是数据类型的无意识溢出。a[i] 本身是 1e9 级别的虽然代码里没有直接算 a[i] - x因为我们根本不需要算具体操作后的数组但读入时还是用 long long 稳妥。离散化用的 vector 也存 long long。如果用 int 读入遇到比较大的边界数据虽然通常也没事但信奥题的评测环境对 UB 很敏感养成 long long 的习惯能省掉不少麻烦。第六个坑是关于 x 的范围。原题里 x 是非负整数所以 x0 是合法操作。我们的推导依赖x 可以足够大但最终答案公式里并没有真的去构造 x这可能导致有人担心万一最优切分点需要的 x 不是整数怎么办。其实 x 只要取一个大于等于 a_i - a_j 1 的整数就可以一定是存在的。这个细节在写题解时容易被忽略但证明了公式的严谨性。除了这些代码层面的坑还有一个思路层面的易错点值得强调。很多人看到区间整体减 x第一反应是枚举操作区间覆盖了哪些 LIS 元素然后试图平衡前后两端的值约束。这种思路不是不行但推导起来非常绕而且很难保证正确性。实际上这个题的最优解一定可以看作把一段前缀或后缀整体压扁这个性质一出问题就从区间 DP 感变成了切分点枚举复杂度直接降下来。所以以后碰到类似区间整体加、减同一个数的 LIS 变种题可以先想想能不能把任意区间限制成前缀或后缀操作。我在本地测试的时候习惯把暴力解和正解对拍。暴力做法很简单枚举所有 l、r、x或者更粗暴一点枚举所有可能的操作后数组再求 LIS数据范围开小一点对拍随机数据能很快找出上面这些边界问题。对拍脚本里我会生成 n 从 1 到 8 的小数据值域 1 到 5跑几百组随机样例暴力正确性有保证正解必须和它完全一致。这个小技巧对于这种思路反直觉的题特别有用强烈建议你也试试。最后分享一个调试小技巧我自己在写 sufLIS 时容易把反向扫描写成从右往左维护以 i 结尾这方向就反了。验证方法很简单拿一个单调递增的数组 [1,2,3,4,5]sufLIS[1] 应该是 5因为可以从 1 一路升到 5如果这里算成了 1说明反向处理逻辑有问题。单调递增和单调递减这两个极端用例几乎能瞬间暴露所有方向错误建议写完扫描逻辑先拿这两组测试打底再去对拍随机数据。