2128D.md (2285B)
1 Source: https://codeforces.com/problemset/problem/2128/D 2 3 D. Sum of LDS 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You're given a permutation$^{\text{∗}}$ $p_1, \ldots, p_n$ such that $\max(p_i, p_{i+1}) \gt p_{i+2}$ for all $1 \leq i \leq n-2$. 22 23 Compute the sum of the length of the longest decreasing subsequence$^{\text{†}}$ of the subarray $[p_l, p_{l+1}, \ldots, p_r]$ over all pairs $1 \leq l \leq r \leq n$. 24 25 $^{\text{∗}}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array). 26 27 $^{\text{†}}$Given an array $b$ of size $|b|$, a decreasing subsequence of length $k$ is a sequence of indices $i_1, \ldots, i_k$ such that: 28 29 * $1 \leq i_1 \lt i_2 \lt \ldots \lt i_k \leq |b|$ 30 * $b_{i_1} \gt b_{i_2} \gt \ldots \gt b_{i_k}$ 31 32 Input 33 34 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10\,000$). The description of the test cases follows. 35 36 The first line of each test case contains a single integer $n$ ($3 \leq n \leq 500\,000$). 37 38 The second line of each test case contains $n$ integers $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$, $p_i$ are pairwise distinct). 39 40 It is guaranteed that $\max(p_i, p_{i+1}) \gt p_{i+2}$ for all $1 \leq i \leq n-2$. 41 42 The sum of $n$ over all test cases does not exceed $500\,000$. 43 44 Output 45 46 For each test case, output the sum over all subarrays of the length of its longest decreasing subsequence. 47 48 Example 49 50 Input 51 52 ``` 53 4 54 55 3 56 57 3 2 1 58 59 4 60 61 4 3 1 2 62 63 6 64 65 6 1 5 2 4 3 66 67 3 68 69 2 3 1 70 ``` 71 72 Output 73 74 ``` 75 10 76 17 77 40 78 8 79 ``` 80 81 Note 82 83 For any array $a$, we define $\text{LDS}(a)$ as the length of the longest decreasing subsequence of $a$. 84 85 In the first test case, all subarrays are decreasing. 86 87 In the second one, we have 88 89 $\text{LDS}([4]) = \text{LDS}([3]) = \text{LDS}([1]) = \text{LDS}([2]) = 1$ 90 91 $\text{LDS}([4,3]) = \text{LDS}([3,1]) = 2, \text{LDS}([1, 2]) = 1$ 92 93 $\text{LDS}([4,3,1]) = 3, \text{LDS}([3,1,2]) = 2$ 94 95 $\text{LDS}([4,3,1,2]) = 3$ 96 97 So the answer is $1+1+1+1+2+2+1+3+2+3=17$.