题目解析

给定一个排列 $p_1, p_2, \dots, p_n$，满足对任意 $1 \le i \le n-2$ 有 $\max(p_i, p_{i+1}) > p_{i+2}$。要求计算所有子数组 $[p_l, \dots, p_r]$ 的最长递减子序列（LDS）的长度之和。

关键性质

在给定条件下，可以证明：对于任意子数组，其 LDS 长度等于子数组的长度减去子数组内“上升相邻对”的数量，其中上升相邻对是指满足 $p_i < p_{i+1}$ 的相邻位置对。等价地，LDS 长度等于子数组内“下降相邻对”的数量加 $1$。

证明思路

1. 整个数组的 LDS 长度：设 $m$ 为满足 $p_i > p_{i+1}$ 的索引 $i$ 的个数。可以证明，这些索引对应的值构成一个递减子序列（利用给定条件），且任何递减子序列最多包含每个“非下降相邻对”中的一个元素，因此 LDS 长度恰好为 $m$。对于长度为 $1$ 的子数组，LDS 长度为 $1$，等于下降对数量 $0$ 加 $1$。

2. 子数组的推广：由于给定条件对所有 $i$ 成立，任意子数组内仍满足该条件（只要三个连续元素都在子数组中）。因此，子数组的 LDS 长度同样等于其内部下降相邻对的数量加 $1$。

3. 下降对与上升对的关系：对于长度为 $len$ 的子数组，有 $len-1$ 个相邻对。下降对数量 $= (len-1) -$ 上升对数量。故 LDS 长度 $= 1 + (len-1 - \text{上升对}) = len - \text{上升对}$。

因此，所有子数组的 LDS 长度之和等于 所有子数组的长度之和 减去 所有子数组中上升相邻对出现的总次数。

计算总和

• 所有子数组的长度之和
  每个位置 $i$（$1 \le i \le n$）被包含在 $i \cdot (n-i+1)$ 个子数组中（左端点有 $i$ 种选择，右端点有 $n-i+1$ 种）。所以：

  $$\text{SumLen} = \sum_{i=1}^{n} i \cdot (n-i+1)$$

  也可直接按子数组长度累加。

• 所有上升相邻对的出现次数
  对于每个 $i$（$1 \le i \le n-1$），若 $p_i < p_{i+1}$，则包含这两个位置的子数组左端点可取 $1 \dots i$，右端点可取 $i+1 \dots n$，共 $i \cdot (n-i)$ 个。

  因此，答案为：

  $$\text{Answer} = \sum_{i=1}^{n} i\,(n-i+1) \;-\; \sum_{i=1}^{n-1} [p_i < p_{i+1}] \cdot i\,(n-i) $$

时间复杂度 $O(n)$，空间 $O(1)$（只需读入数组）。所有测试用例 $n$ 总和不超过 $5\times10^5$，满足要求。

算法步骤

对于每个测试用例：

1. 读入 $n$ 和排列 $p$。
2. 计算总长度和 sum_len = 0，遍历 $i=1$ 到 $n$，累加 $i \cdot (n-i+1)$。
3. 遍历 $i=1$ 到 $n-1$，若 $p_i < p_{i+1}$，则从 sum_len 中减去 $i \cdot (n-i)$。
4. 输出 sum_len。

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> p(n);
        for (int i = 0; i < n; ++i) cin >> p[i];
        ll total = 0;
        for (int i = 1; i <= n; ++i) {
            total += (ll)i * (n - i + 1);
        }
        for (int i = 0; i < n - 1; ++i) {
            if (p[i] < p[i+1]) {
                total -= (ll)(i+1) * (n - i - 1);
            }
        }
        cout << total << '\n';
    }
    return 0;
}

示例验证

• 样例1：$n=3,\ p=[3,2,1]$，无上升对，$total = 1\cdot3+2\cdot2+3\cdot1=10$，输出 $10$。
• 样例2：$n=4,\ p=[4,3,1,2]$，上升对仅 $i=3$（$1<2$），$total=1\cdot4+2\cdot3+3\cdot2+4\cdot1=20$，减去 $3\cdot1=3$，得 $17$。
• 样例3：$n=6,\ p=[6,1,5,2,4,3]$，计算可得 $40$，与输出一致。
• 样例4：$n=3,\ p=[2,3,1]$，上升对 $i=1$（$2<3$），$total=10$，减去 $1\cdot2=2$，得 $8$。

所有结果与样例完全匹配。