D. Sum of LDS

问题描述

给定一个长度为 $n$ 的排列 $p_1, p_2, \ldots, p_n$（即一个包含从 $1$ 到 $n$ 的每个整数恰好一次的数组），其性质为对于每个 $1 \leq i \leq n-2$：

对于每一对索引 $1 \leq l \leq r \leq n$，考虑子数组 $[p_l, p_{l+1}, \ldots, p_r]$。令 $LDS(l, r)$ 表示该子数组中最长递减子序列的长度。

计算总和：

定义：

• 一个长度为 $n$ 的 排列 是一个由 $n$ 个从 $1$ 到 $n$ 的不同整数按任意顺序组成的数组。
• 数组 $b$ 中长度为 $k$ 的 递减子序列 是一个索引序列 $i_1 < i_2 < \ldots < i_k$，使得 $b_{i_1} > b_{i_2} > \ldots > b_{i_k}$。

题解概述

让我们逐步分析问题：

1. 关键约束： 条件 $\max(p_i, p_{i+1}) > p_{i+2}$ 确保了排列中不会出现连续两次上升。

2. LDS 贡献： 对于任何一对 $(p_i, p_{i+1})$ 其中 $p_i > p_{i+1}$，这两个元素形成一个“块”，可以对任何包含它们的子数组的最长递减子序列（LDS）做出贡献。然而，实际上只有其中一个会增加LDS的长度。

3. 计算贡献： 对于每个这样的对 $(p_i, p_{i+1})$ 其中 $p_i > p_{i+1}$，包含它们的子数组数量为 $(i + 1) \times (n - i - 1)$，其中 $i$ 是 $p_i$ 的索引（0-based）。

4. LDS 总和： 如果没有这样的对，总和就是所有子数组长度的总和：

   $$n + 2(n-1) + 3(n-2) + \ldots + n$$

   否则，对于每个 $p_i > p_{i+1}$ 的对 $(p_i, p_{i+1})$，减去多计算的贡献。这部分可以用 $O(1)$ 优化，但我没有实现。

5. 算法步骤：

   • 遍历排列并识别所有 $p_i > p_{i+1}$ 的对 $(p_i, p_{i+1})$。
   • 对于每个这样的对，从LDS总和中减去 $(i + 1) \times (n - i - 1)$。
   • 输出最终结果。

这种方法利用了排列的结构，并有效地计算了所需的总和。

提交链接