1. 项目概述从一道国赛真题看“本质上升子序列”如果你正在备战蓝桥杯国赛或者对动态规划DP中的经典问题“最长上升子序列LIS”已经滚瓜烂熟那么“本质上升子序列”这道题很可能就是你通往更高分路上的一个关键路标。我第一次在模拟卷上遇到它时也愣了一下——不就是LIS吗但仔细一看题目描述和样例才发现里面藏着不少“坑”和“本质”的区别。这道题经常出现在国赛级别的模拟测试或真题中考察的不仅仅是你会不会套LIS的模板更是你对问题本质的理解、对状态定义的精准把握以及处理去重等边界条件的代码实现能力。简单来说它要求你计算一个序列中所有值不同的上升子序列的数量。注意是“本质不同”即子序列作为一个序列其元素构成不同才算不同的序列而不是位置不同。这直接拔高了题目的难度和思考深度。今天我就结合多次模拟测试和实战的经验把这题从里到外拆解清楚让你不仅会做更能理解其背后的动态规划思想与优化技巧从容应对国赛。2. 问题核心定义、区别与难点剖析2.1 什么是“本质上升子序列”我们先明确概念。给定一个长度为n的整数序列a[1...n]。普通上升子序列一个序列b如果它是a的子序列即从a中删除一些元素后得到并且b中的元素严格单调递增那么b就是a的一个上升子序列。本质上升子序列在普通上升子序列的基础上附加了一个条件只计数“本质不同”的子序列。也就是说如果两个上升子序列b1和b2虽然来自a的不同位置但只要它们包含的元素值完全相同顺序也相同它们就被视为同一个子序列只计算一次。举个例子序列a [1, 2, 2, 3]。它的普通上升子序列有很多比如[1],[2]来自第一个2[2]来自第二个2[1, 2]取第一个1和第一个2[1, 2]取第一个1和第二个2[2, 3],[1, 2, 3]等等。但它的本质上升子序列是哪些呢[1],[2],[1, 2],[3],[1, 3],[2, 3],[1, 2, 3]。注意这里[2]只算一个尽管在a中出现了两次同样[1, 2]也只算一个。所以本质不同的上升子序列总数是7。2.2 与经典LIS问题的根本区别很多同学一看到“上升子序列”第一反应就是动态规划求长度状态定义为dp[i]表示以a[i]结尾的最长上升子序列长度。但“本质上升子序列”要求的是数量而且是去重后的数量。这带来了几个根本性的区别目标不同经典LIS求的是最大长度一个数值本题求的是所有不同序列的总数一个数值。状态定义迁移求数量时dp[i]通常定义为以a[i]结尾的、满足条件的子序列的个数。但直接套用会遇到严重的重复计数问题。去重是核心难点如何避免对值相同的子序列进行重复计数是本题最大的挑战。例如上例中以第一个2和第二个2结尾的、内容为[2]的子序列我们只能算一次。以它们结尾的、内容为[1, 2]的子序列也只能算一次。2.3 常见错误思路与难点解析在模拟测试中我见过也自己犯过以下几种典型错误错误思路1暴力枚举集合去重。生成所有可能的子序列判断是否上升然后放入一个集合Set中去重。理论上可行但时间复杂度是 O(2^n)n稍微大一点比如50就完全不可行。国赛数据规模通常n在 1000 以上甚至 10^5这条路走不通。错误思路2简单修改LIS的DP计数。定义dp[i]为以a[i]结尾的本质上升子序列个数。转移时dp[i] 1 sum(dp[j])其中j i且a[j] a[i]。这个思路的问题在于它会把所有以a[j]结尾的子序列后面接上a[i]但对于值相同的a[i]比如多个相同的2从不同j转移过来可能会产生内容完全相同但结尾位置不同的子序列导致重复计数。例如对于a [1, 2, 2]按此计算dp[1]1 ([1]),dp[2]1dp[1]2 ([2], [1,2])dp[3]1dp[1]2 ([2], [1,2])总和为5。但实际上本质不同的只有[1],[2],[1,2]这3个。这里dp[2]和dp[3]都计算了[2]和[1,2]导致重复。难点如何设计状态和转移方程使得对于每个不同的子序列值组合只在它“第一次”可能被生成的位置被计数一次这就需要我们更精细地考虑“以某个值结尾”而不是“以某个位置结尾”。注意这里的“第一次”是一个关键思想。我们需要保证对于任何一个本质上升子序列当它的最后一个元素最大值在序列中首次出现时我们就完成对它的计数后续再出现相同的值就不再重复计数。3. 核心解决方案基于“结尾值”的动态规划经过对问题的拆解我们意识到需要摆脱“以位置i结尾”的思维定式转而采用“以数值v结尾”的状态定义。这是解决去重问题的关键一跳。3.1 状态定义与转移方程我们假设序列a中元素的取值范围是有限的或者我们可以对其进行离散化这是处理大数据范围的常用技巧。设所有可能出现的数值经过排序和映射后得到一个从1到M的整数范围。我们定义dp[v]表示以数值v结尾的、本质不同的上升子序列的个数。现在考虑如何转移。对于一个本质上升子序列它的最后一个元素是v。那么它可能由两种方式构成子序列只包含v本身即[v]。子序列由某个以小于v的数值u结尾的子序列后面加上v构成。因此转移方程可以初步写为dp[v] 1 sum(dp[u])其中u是所有小于v的、在序列中出现过的数值。但是这里还有一个关键点我们是在遍历原序列a的过程中来计算dp的。当我们处理到a[i] v时我们需要用当前时刻所有小于v的dp[u]之和来更新dp[v]。并且如果序列中后面又出现了另一个v我们该如何处理根据“本质不同”的原则后面出现的相同值v不应该产生新的、以v结尾的本质子序列因为所有可能的以v结尾的子序列在第一次遇到v时就已经被枚举了。所以我们得到最终的处理逻辑初始化一个数组dp长度为M1数值范围所有元素为0。同时维护一个前缀和数组prefix_sum用于快速计算所有小于v的dp值之和。遍历原序列a的每一个元素x。对于当前的x我们计算sum 1 prefix_sum[x-1]。这里的1代表子序列[x]prefix_sum[x-1]代表所有以小于x的值结尾的子序列后面接上x所能形成的新子序列数量。然后我们检查dp[x]的当前值。如果dp[x]是0说明这是第一次遇到数值x。那么dp[x]的新值就是sum。接着我们需要更新前缀和数组prefix_sum从索引x开始到M每个位置都加上sum因为新增加了sum个以x结尾的子序列所有大于x的数值在后续计算时都应该能“看到”这些新序列作为转移来源。如果dp[x]不是 0说明之前已经遇到过x。根据本质不同的原则此时新增的子序列都是重复的。但是注意我们的sum计算是基于当前的前缀和它包含了之前所有小于x的dp值。这次计算出的sum与第一次计算出的dp[x]的差值就代表了由于在第一次遇到x之后序列中又出现了新的、小于x的数值所构成的子序列这些子序列后面接上当前这个x会形成新的、以前未计数过的、以x结尾的本质子序列吗答案是不会。因为子序列的结尾值已经是x而序列内容是本质不同的关键。在第一次遇到x时所有可能的小于x的结尾值都已经在prefix_sum中被考虑了尽管它们对应的子序列数量后续可能会增长。后续再遇到x用增长后的prefix_sum计算得到的sum增量实际上对应的是“在第一次遇到x之后才出现的小于x的元素”与“当前这个x”组成的序列。但这些序列是否与之前已有的以x结尾的序列重复仔细思考假设之前有一个以u结尾的子序列S在第一次遇到x时S[x]已经被计入dp[x]。现在在第一次遇到x之后序列中又出现了一个新的数值ww x并且形成了新的以w结尾的子序列T。那么T[x]这个序列它的结尾是x内容与S[x]不同因为T不同于S。它应该是一个新的本质子序列所以当再次遇到x时我们需要增加的是这部分“新出现的小于x的结尾值所构成的新子序列”后面接上x所产生的数量即sum - dp[x]。然后更新dp[x] (sum - dp[x])并同样更新前缀和。简化实现实际上我们可以统一处理。无论dp[x]是否为0我们都计算sum 1 prefix_sum[x-1]。那么本次对总答案的新增贡献就是sum - dp[x]。然后我们执行dp[x] sum并更新前缀和将sum - old_dp[x]这个增量加到从x开始的前缀和上。当dp[x]初始为0时sum - 0 sum逻辑与第一种情况一致。3.2 算法流程与示例演算让我们用a [1, 2, 2, 3]来手动演算一下假设数值范围M3。初始化dp [0,0,0,0]索引1到3prefix_sum [0,0,0,0]同样索引1到3prefix_sum[i]表示dp[1]到dp[i]的和。遍历a[0]1sum 1 prefix_sum[0] 1 0 1。prefix_sum[0]我们视为0新增贡献delta sum - dp[1] 1 - 0 1。更新dp[1] 1。更新前缀和从索引1开始prefix_sum[1] 1prefix_sum [0,1,1,1]为了快速更新我们通常用树状数组或线段树这里用朴素描述理解。实际上prefix_sum变为[0,1,1,1]表示dp[1]1, dp[2]0, dp[3]0的和是1。总答案ans 1。遍历a[1]2sum 1 prefix_sum[1] 1 1 2。prefix_sum[1]是dp[1]的和即1delta sum - dp[2] 2 - 0 2。更新dp[2] 2。更新前缀和从索引2开始prefix_sum[2] 2prefix_sum [0,1,3,3]。ans 1 2 3。解释新增的2个子序列是[2]和[1,2]。遍历a[2]2第二个2sum 1 prefix_sum[1] 1 1 2。注意prefix_sum[1]仍然是1因为dp[1]没变过delta sum - dp[2] 2 - 2 0。更新dp[2] 2不变。更新前缀和增量为0所以不更新。ans 3 0 3。解释没有新增任何本质不同的以2结尾的子序列。遍历a[3]3sum 1 prefix_sum[2] 1 3 4。prefix_sum[2]是dp[1]dp[2]123delta sum - dp[3] 4 - 0 4。更新dp[3] 4。更新前缀和从索引3开始prefix_sum[3] 4prefix_sum [0,1,3,7]。ans 3 4 7。解释新增的4个子序列是[3],[1,3],[2,3],[1,2,3]。最终结果ans 7与之前分析一致。3.3 数据结构优化树状数组Fenwick Tree在上面的流程中我们频繁进行两种操作查询前缀和prefix_sum[x-1]。单点更新后更新前缀和将delta加到dp[x]上并需要将delta加到所有prefix_sum[j]j x上。朴素的前缀和数组在更新时需要O(M)的时间总时间复杂度为O(n * M)在M很大时不可接受。这正是树状数组或线段树的经典应用场景。树状数组可以在O(log M)的时间内完成单点更新和前缀和查询。因此我们的算法优化为初始化一个树状数组bit长度为M1初始为0。bit维护的就是我们上面提到的dp数组的树状结构bit.query(x)可以快速得到prefix_sum[x]即dp[1]到dp[x]的和。遍历序列a的每个元素x离散化后的值。sum 1 bit.query(x-1)。delta sum - current_dp_value。我们需要知道current_dp_value可以额外用一个数组dp_val记录也可以再用一个树状数组不我们只需要知道dp[x]的当前值。我们可以用一个数组last来记录每个数值x对应的当前dp[x]值。last[x] sum。bit.update(x, delta)。这个操作会将delta加到dp[x]上并更新树状数组。ans delta。这样总时间复杂度就降到了O(n log M)通常可以应对n和M在10^5级别的数据。4. 完整代码实现与逐行解析下面给出基于C的完整实现包含离散化步骤和树状数组优化。我假设输入序列a的长度为n存储在vectorint a中。#include iostream #include vector #include algorithm using namespace std; const int MOD 1000000007; // 通常结果会要求取模这里先加上 // 树状数组类 class Fenwick { private: vectorlong long tree; int n; public: Fenwick(int size) : n(size), tree(size 1, 0) {} // 更新位置x增加delta void update(int x, long long delta) { while (x n) { tree[x] (tree[x] delta) % MOD; x x -x; } } // 查询前缀和 [1, x] long long query(int x) { long long res 0; while (x 0) { res (res tree[x]) % MOD; x - x -x; } return res; } }; int main() { int n; cin n; vectorint a(n); for (int i 0; i n; i) { cin a[i]; } // 1. 离散化 vectorint b a; sort(b.begin(), b.end()); b.erase(unique(b.begin(), b.end()), b.end()); // 去重得到所有不同的值 int m b.size(); // 离散化后的数值范围 // 离散化映射函数 auto get_id [](int val) { return lower_bound(b.begin(), b.end(), val) - b.begin() 1; // 映射到1..m }; // 2. 初始化树状数组和dp值记录数组 Fenwick bit(m); vectorlong long last(m 1, 0); // last[i] 记录离散化后值i对应的当前dp值 long long ans 0; // 3. 遍历原序列 for (int val : a) { int id get_id(val); // 获取离散化后的id // 计算以当前值结尾的新增子序列数量 // sum 1 (序列[val]自身) 所有小于val的结尾值对应的子序列总数 long long sum (1 bit.query(id - 1)) % MOD; // 新增的、不重复的部分 sum - 上一次计算出的以val结尾的子序列数 long long delta (sum - last[id] MOD) % MOD; // 加MOD防止负数 if (delta 0) { // 更新树状数组相当于更新了dp[id] bit.update(id, delta); // 更新last记录 last[id] sum; // 累加答案 ans (ans delta) % MOD; } } cout ans endl; return 0; }逐行解析与关键点离散化这是处理数值范围大但数量有限的经典操作。b数组存储了a中所有不同的值并排序。get_id函数通过二分查找将原值映射到1到m的连续整数。这保证了树状数组的大小m与序列中不同元素的数量相关而不是与原值范围相关极大提升了效率。树状数组bit它维护的是离散化后以每个值id结尾的dp值即本质上升子序列个数的树状结构。bit.query(id-1)就等价于我们之前分析的prefix_sum[id-1]即所有小于当前值的dp之和。数组last用于记录每个离散化后的值id对应的、当前计算出的dp值即last[id]。我们需要它来计算delta。核心循环sum 1 bit.query(id - 1)计算理论上以当前值val结尾的所有可能的新子序列数量包括可能重复的。delta sum - last[id]这是精髓。last[id]是之前计算出的、以val结尾的子序列数量。sum是基于当前所有小于val的子序列信息重新计算的总数。它们的差值delta就是自从上一次处理val之后由于新出现的小于val的元素所产生的新子序列后面接上当前这个val所构成的、全新的、以前没计数过的本质子序列数量。如果delta为0说明没有新增。bit.update(id, delta)将这新增的delta个子序列数量累加到树状数组的id位置。这相当于更新了dp[id]并且这个更新会影响到所有大于id的位置的前缀和查询。last[id] sum更新记录。ans delta将新增的数量加入总答案。取模题目通常要求结果对一个大质数如1e97取模。我们在所有加法和更新操作中都进行了取模并在计算delta时(sum - last[id] MOD) % MOD防止负数出现。5. 常见问题、调试技巧与扩展思考5.1 典型错误与排查错误结果比预期小很多。检查点1离散化是否正确确保get_id函数对相同的原值返回相同的id。lower_bound在排序后的b中查找是正确的。检查点2delta的计算和更新逻辑。确认是sum - last[id]而不是sum - bit.query(id)。bit.query(id)是前缀和不是dp[id]的当前值。last数组是必须的。检查点3初始化。last数组初始为0bit初始全0。ans初始为0。检查点4取模运算。在取模环境下delta可能为负数当sum last[id]时虽然理论上不会但取模后可能发生。所以要用(sum - last[id] MOD) % MOD。错误结果溢出或不对未取模时。检查点数据范围。本质上升子序列的数量可能增长非常快指数级。n较大时数量会超过long long的范围。务必在计算过程中就进行取模而不是最后才取模。sum、delta、ans的每一次运算都要取模。错误遇到重复元素时答案错误。核心检查再次理解delta的含义。当第二次遇到val时sum是基于当前所有小于val的子序列总数计算的。如果在这两次val之间没有出现新的、小于val的数值或者这些新数值没有形成新的子序列那么sum不会变delta为0正确。如果出现了新的、小于val的数值并形成了新子序列那么sum会增大delta就是这些新子序列接上当前val所产生的新序列数。这是符合“本质不同”定义的。5.2 调试技巧小数据手工模拟就像我们前面用[1,2,2,3]做的那样在纸上或注释里写出每一步的id,sum,last[id],delta,bit的状态可以打印bit.tree数组以及ans。这是理解算法和定位错误最有效的方法。打印关键变量在循环内打印每个元素的id,sum,last[id],delta。测试边界用例空序列答案应为0。所有元素相同如[5,5,5]本质上升子序列只有[5]一个答案应为1。严格递增序列如[1,2,3]本质上升子序列为[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]共7个。严格递减序列如[3,2,1]本质上升子序列为[3],[2],[1]共3个。5.3 扩展思考与变种如果不要求“本质不同”而是求所有上升子序列的数量包括位置不同。这个问题更简单。定义dp[i]为以第i个元素结尾的上升子序列个数。转移方程dp[i] 1 sum(dp[j])对于所有j i且a[j] a[i]。总答案就是sum(dp[i])。可以用树状数组优化到O(n log n)。与本题的区别在于它不关心子序列是否由相同的值构成只关心位置。所以每个位置都是独立的即使值相同。如果要求输出具体的本质上升子序列而不仅仅是数量。难度暴增。数量可能是指数级的无法全部输出。通常题目会限制条件比如只输出字典序第K小的。这就需要结合DP计数和递归构造是更高级的题型。“本质不下降子序列”数量。将条件从严格递增 () 改为非严格递增 ()。此时状态转移时对于相同的值也需要考虑转移。但“本质不同”的定义依然存在。解法类似但在离散化和比较时需要小心。通常为了处理我们可以在离散化时保留相同值但在树状数组查询时查询的是bit.query(id)包含等于的情况而不是id-1。同时去重的逻辑需要调整当遇到相同的val时新产生的子序列可能会与之前val产生的序列重复吗会的。例如[1,2,2]以第二个2结尾的[1,2]与以第一个2结尾的[1,2]是同一个本质子序列。所以我们的delta计算逻辑sum - last[id]依然有效但这里的sum计算用的是bit.query(id)。5.4 国赛实战建议理解优先于记忆不要死记硬背这个题的代码。务必理解“以值结尾”的状态定义、delta去重的原理、以及树状数组如何优化前缀和查询与更新。这样即使题目稍有变化比如求长度不超过K的本质上升子序列数量你也能灵活调整。模板化组件将离散化、树状数组这两个通用组件写成自己熟悉的模板比赛时能快速无误地敲出来。仔细审题国赛题目的描述往往非常精确。一定要分清是“本质不同”还是“位置不同”是“上升”还是“不下降”结果是否取模。测试用例编码完成后务必用上面提到的几个边界用例和简单用例测试确保基本逻辑正确。