Problem Statement

给定一个排列 $ ^{\text{∗}} $ $ p_1, \ldots, p_n $，满足对于所有 $ 1 \leq i \leq n-2 $ 都有 $ \max(p_i, p_{i+1}) > p_{i+2} $。

计算所有子数组 $ [p_l, p_{l+1}, \ldots, p_r] $（其中 $ 1 \leq l \leq r \leq n $）的最长递减子序列 $ ^{\text{†}} $ 长度的总和。

$ ^{\text{∗}} $ 长度为 $ n $ 的排列是指由 $ 1 $ 到 $ n $ 的 $ n $ 个不同整数按任意顺序组成的数组。例如，$ [2,3,1,5,4] $ 是一个排列，但 $ [1,2,2] $ 不是排列（因为 $ 2 $ 出现了两次），$ [1,3,4] $ 也不是排列（当 $ n=3 $ 时出现了 $ 4 $）。

$ ^{\text{†}} $ 给定一个大小为 $ |b| $ 的数组 $ b $，长度为 $ k $ 的递减子序列是指满足以下条件的下标序列 $ i_1, \ldots, i_k $：

• $ 1 \leq i_1 < i_2 < \ldots < i_k \leq |b| $
• $ b_{i_1} > b_{i_2} > \ldots > b_{i_k} $

Input

每个测试包含多个测试用例。第一行包含测试用例的数量 $ t $（$ 1 \le t \le 10,000 $）。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $ n $（$ 3 \leq n \leq 500,000 $）。

每个测试用例的第二行包含 $ n $ 个整数 $ p_1, p_2, \ldots, p_n $（$ 1 \le p_i \le n $，且所有 $ p_i $ 互不相同）。

保证对于所有 $ 1 \leq i \leq n-2 $ 都有 $ \max(p_i, p_{i+1}) > p_{i+2} $。

所有测试用例的 $ n $ 之和不超过 $ 500,000 $。

Solving

套路题，线性枚举累加贡献，注意dp[i]枚举子数组时的定义方式

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

void solve()
{   
    int n;
    cin >> n;
    vector<int> p(n+1);
    vector<int> dp(n+1); // dp[i] 表示每个1~i每个下标到i构成的子数组中LDS的总和
    for(int i=1;i<=n;i++) cin >> p[i];
    int ans = 0;
    dp[1] = 1;
    dp[2] = (p[2] > p[1]) ? 2 : 3;
    ans += dp[1] + dp[2];
    for(int i=3;i<=n;i++)
    {   
        // 讨论p[i-1]和p[i-2]哪一个是大于p[i]的那一个
        if(p[i-1] > p[i]) dp[i] = dp[i-1] + i;
        else dp[i] = dp[i-1] + 1;
        ans += dp[i];
    }
    cout << ans << endl;
}