红心女王的扑克士兵: 补充解法¶

树状数组维护严格下降子序列¶

本方法及 C++17 实现由 Codex（GPT-6）补充。完整程序见 alternative.cpp。排序归约和出题人的原解法见主题解。

按攻击力递增、同攻击力时防御力递增排序。令 \(D_i\) 为以第 \(i\) 个士兵结尾的最长严格下降防御力子序列长度，则

\[ D_i=1+\max_{j<i,\ Armor_j>Armor_i}D_j \]

空集合的最大值按零处理。把所有防御力的相反数排序去重并离散化，较大防御力对应较小排名。用树状数组维护每个排名处已经得到的最大 \(D\) ；查询当前排名之前的前缀最大值，加一得到 \(D_i\) ，再用它更新当前排名。所有 \(D_i\) 的最大值就是答案，空输入给零。

任何以 \(i\) 结尾、长度大于一的可行子序列，去掉末项后一定落在上述候选集合；反过来，每个候选都可追加 \(i\) .这证明递推式。树状数组在处理 \(i\) 前恰好保存先前各项的最优值，因此归纳得到所有 \(D_i\) 正确。同攻击力的先前士兵防御力不大于当前值，不会进入严格查询范围，无需延迟这一组的更新。

排序、离散化及查询更新总计 \(O(n\log(n+1))\) 时间，空间 \(O(n)\) .相反数在给定属性范围内不会溢出。该方案具有动态规划含义和可扩展的区间统计结构，但与标准链覆盖算法同阶、数组更多，实测常数也较大，不作为无条件优化。