D. Sum of LDS - 题解

比赛与标签

比赛: Codeforces Round 1039 (Div. 2) 标签: brute force, combinatorics, dp, greedy, math 难度: *1800

喵喵，这是什么任务呀？ - 题目大意

主人，我们接到了一个有趣的任务！(ฅ'ω'ฅ)

我们得到了一个长度为 n 的排列 p（也就是 1 到 n 这些数字不重不漏地排列一次）。这个排列很特别，它满足一个神奇的性质：对于任意 1 ≤ i ≤ n-2，都有 max(p_i, p_{i+1}) > p_{i+2}。

我们的目标是，计算出这个排列 p 的 所有 连续子数组 p[l..r] 的“最长下降子序列”（Longest Decreasing Subsequence, LDS）的长度之和。

简单来说，就是对所有可能的 1 ≤ l ≤ r ≤ n，我们都求一遍 LDS(p[l..r]) 的长度，然后把这些长度全部加起来！是不是听起来就很有挑战性呐？

解谜时间到！- 解题思路

直接暴力枚举所有 O(n^2) 个子数组，再对每个子数组求 LDS（通常需要 O(k log k) 的时间，k 是子数组长度），总时间复杂度会达到 O(n^3 log n) 左右，这对于 n 高达 500,000 的数据规模来说，是绝对会超时的说！

所以，我们得想个更聪明的办法，喵~ 这种求和问题，通常都可以往动态规划（DP）的方向思考！

我们的目标是计算 TotalSum = sum_{l=1 to n} sum_{r=l to n} LDS(p[l..r])。

我们可以换个角度，先固定左端点 l，计算从 l 开始的所有子数组的 LDS 长度之和。 我们定义一个 DP 数组 T，让 T[l] = sum_{r=l to n} LDS(p[l..r])。 那么最终的答案就是 sum_{l=1 to n} T[l]。

现在，关键问题就变成了如何快速计算 T[l]。我们可以尝试从后往前计算，看看 T[l] 和 T[l+1]、T[l+2] 等之间有没有什么关系。

T[l] = LDS(p[l..l]) + sum_{r=l+1 to n} LDS(p[l..r])T[l] = 1 + sum_{r=l+1 to n} LDS(p[l..r])

而 T[l+1] = sum_{r=l+1 to n} LDS(p[l+1..r])。

所以，T[l] 和 T[l+1] 的关系，就取决于 LDS(p[l..r]) 和 LDS(p[l+1..r]) 的关系。

这时候，题目给的那个神奇性质 max(p_i, p_{i+1}) > p_{i+2} 就派上大用场了！这个性质告诉我们，一个排列中不可能出现 p_i < p_{i+1} < p_{i+2} 这种连续上升的情况。它极大地简化了子序列的结构！一个非常重要的推论是：对于任何子数组，它的最长下降子序列（LDS）总可以被构造成从该子数组的第一个或第二个元素开始。

有了这个强大的推论，我们就可以分两种情况来寻找递推关系啦！

---

情况一：p[l-1] > p[l] (数组中是 p_l > p_{l+1})

当 p_l 比紧跟着它的 p_{l+1} 大时，对于任何以 l 开头的子数组 p[l..r]（其中 r > l），它的 LDS 都可以通过在 p[l+1..r] 的 LDS 前面加上 p_l 得到。因为 p_l 足够大，可以“接纳”后面任何一个下降子序列。 所以，我们能得出一个美妙的结论：LDS(p[l..r]) = 1 + LDS(p[l+1..r])。

把这个关系代入 T[l] 的定义中： T[l] = 1 + sum_{r=l+1 to n} LDS(p[l..r])T[l] = 1 + sum_{r=l+1 to n} (1 + LDS(p[l+1..r]))T[l] = 1 + (n - l) + sum_{r=l+1 to n} LDS(p[l+1..r])T[l] = (n - l + 1) + T[l+1]

看，第一个递推公式就出来啦！喵~

---

情况二：p[l-1] < p[l] (数组中是 p_l < p_{l+1})

当 p_l 比 p_{l+1} 小的时候，根据题目的性质 max(p_l, p_{l+1}) > p_{l+2}，必然有 p_{l+1} > p_{l+2}。这就形成了一个 p_l < p_{l+1} > p_{l+2} 的小山峰结构！

这次我们来找 T[l] 和 T[l+2] 的关系。 我们来证明一个新结论：当 p_l < p_{l+1} 时，对于任意 r >= l+2，有 LDS(p[l..r]) = 1 + LDS(p[l+2..r])。

• 首先，LDS(p[l+1..r]) = 1 + LDS(p[l+2..r])，这是因为 p_{l+1} > p_{l+2}，符合我们情况一的逻辑。
• 其次，LDS(p[l..r]) 可以从 p_l 或 p_{l+1} 开始。
  • 如果从 p_{l+1} 开始，其长度就是 LDS(p[l+1..r]) = 1 + LDS(p[l+2..r])。
  • 如果从 p_l 开始，因为 p_l < p_{l+1}，所以 p_{l+1} 不能被包含在后面，这个LDS只能从 p[l+2..r] 中寻找小于 p_l 的元素。它的长度不会超过 1 + LDS(p[l+2..r])。
• 综合来看，LDS(p[l..r]) 的最大长度就是 1 + LDS(p[l+2..r])。

有了这个结论，我们再来推导 T[l]： T[l] = LDS(p[l..l]) + LDS(p[l..l+1]) + sum_{r=l+2 to n} LDS(p[l..r])LDS(p[l..l]) 长度是 1。 LDS(p[l..l+1]) 因为 p_l < p_{l+1}，所以最长下降子序列只有一个元素，长度也是 1。 T[l] = 1 + 1 + sum_{r=l+2 to n} (1 + LDS(p[l+2..r]))T[l] = 2 + (n - (l+2) + 1) + sum_{r=l+2 to n} LDS(p[l+2..r])T[l] = 2 + (n - l - 1) + T[l+2]T[l] = (n - l + 1) + T[l+2]

第二个递推公式也顺利诞生啦！(＾▽＾)

---

总结一下我们的DP策略：

1. 从后往前计算 T 数组。
2. Base Case: T[n] = LDS(p[n..n]) = 1。为了方便递推，T[n+1] 和 T[n+2] 都可以看作是 0。
3. 递推:
   • 如果 p[l-1] > p[l], 则 T[l] = (n - l + 1) + T[l+1]。
   • 如果 p[l-1] < p[l], 则 T[l] = (n - l + 1) + T[l+2]。
4. 计算出所有 T[l] 后，把它们加起来 sum_{l=1 to n} T[l] 就是最终答案！

魔法咒语来啦！- 代码实现

#include <iostream>
#include <vector>
#include <numeric>

// Function to solve a single test case
void solve() {
    int n;
    std::cin >> n;
    std::vector<int> p(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> p[i];
    }

    // T[l] 将存储所有以索引 l (1-based) 开始的子数组的LDS长度之和。
    // 即 T_l = sum_{r=l to n} LDS(p[l..r])
    // 我们使用1-based索引来定义T，这样逻辑更清晰，所以T的大小是 n+2。
    // T[n+1] = 0 (对应空范围的和)
    // T[n+2] = 0 (为了 p_l < p_{l+1} 时的递推)
    std::vector<long long> T(n + 2, 0);

    // Base case: l=n。唯一的子数组是 p[n..n]，它的LDS长度是1。
    // 所以 T[n] = LDS(p[n..n]) = 1。
    T[n] = 1;

    // 我们从 l = n-1 向下递推到 l = 1 来计算 T[l]。
    // 递推关系取决于 p_l > p_{l+1} 还是 p_l < p_{l+1}。
    // 在代码中，p是0-indexed，所以 p_l 对应 p[l-1]，p_{l+1} 对应 p[l]。
    for (int l = n - 1; l >= 1; --l) {
        if (p[l - 1] > p[l]) {
            // 情况一的递推公式: p_l > p_{l+1} => T_l = (n - l + 1) + T_{l+1}
            T[l] = (long long)(n - l + 1) + T[l + 1];
        } else { // p_l < p_{l+1}
            // 情况二的递推公式: p_l < p_{l+1} => T_l = (n - l + 1) + T_{l+2}
            T[l] = (long long)(n - l + 1) + T[l + 2];
        }
    }

    // 总答案就是所有 T[l] 的和 (l从1到n)
    long long total_sum = 0;
    for (int l = 1; l <= n; ++l) {
        total_sum += T[l];
    }
    std::cout << total_sum << '\n';
}

int main() {
    // 快速I/O，让程序跑得更快喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

喵，跑得快不快？- 复杂度分析

• 时间复杂度: O(n) 的说。对于每个测试用例，我们只需要一个循环从 n-1 到 1 来填充DP数组 T，然后再用一个循环把 T 的所有元素加起来。两个循环都是线性的，所以总时间复杂度是 O(n)！非常高效！
• 空间复杂度: O(n) 的说。我们需要一个大小为 n 的向量 p 来存储输入的排列，还需要一个大小为 n+2 的DP数组 T。所以空间是线性的。

小猫咪的笔记时间~ - 知识点与总结

这道题真是一次有趣的思维锻炼呢！本猫娘总结了几个要点哦：

1. 动态规划 (DP): 面对看似复杂的求和问题，特别是与子结构（如子数组、子序列）相关的，DP是一个非常强大的武器。定义好状态，找到递推关系，问题就迎刃而解啦。
2. 问题转化: 将 sum_l sum_r 形式的求和，转化为 sum_l (sum_r ...)，然后对括号内的部分进行DP，是一种非常常见的优化思路。
3. 利用特殊性质: 这道题的灵魂就在于 max(p_i, p_{i+1}) > p_{i+2} 这个条件！如果忽略它，这就是一道超级难题。所以，解题时一定要仔细分析题目给的所有条件，它们往往是解题的突破口！
4. 倒序DP: 当 dp[i] 的状态依赖于 dp[i+1], dp[i+2] 等未来的状态时，从后往前（n -> 1）进行DP是一个自然而然的选择。
5. 索引处理: 代码中对DP数组 T 使用1-based索引，而对输入数组 p 使用0-based索引，这种混合使用只要处理得当，就能让递推公式和代码实现完美对应，非常清晰。

总之，遇到难题不要怕，先冷静下来分析题目特性，大胆猜想和推导，说不定就能发现柳暗花明的新大陆喵！加油哦，主人！(๑•̀ㅂ•́)و✧