codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$.