Decinc Dividing solution codeforces – Let’s call an array 𝑎a of 𝑚m integers 𝑎1,𝑎2,…,𝑎𝑚a1,a2,…,am Decinc if 𝑎a can be made increasing by removing a decreasing subsequence (possibly empty) from it.
Table of Contents
[Solution] Decinc Dividing solution codeforces
- For example, if 𝑎=[3,2,4,1,5]a=[3,2,4,1,5], we can remove the decreasing subsequence [𝑎1,𝑎4][a1,a4] from 𝑎a and obtain 𝑎=[2,4,5]a=[2,4,5], which is increasing.
You are given a permutation 𝑝p of numbers from 11 to 𝑛n. Find the number of pairs of integers (𝑙,𝑟)(l,r) with 1≤𝑙≤𝑟≤𝑛1≤l≤r≤n such that 𝑝[𝑙…𝑟]p[l…r] (the subarray of 𝑝p from 𝑙l to 𝑟r) is a Decinc array.
The first line contains a single integer 𝑛n (1≤𝑛≤2⋅1051≤n≤2⋅105) — the size of 𝑝p.
The second line contains 𝑛n integers 𝑝1,𝑝2,…,𝑝𝑛p1,p2,…,pn (1≤𝑝𝑖≤𝑛1≤pi≤n, all 𝑝𝑖pi are distinct) — elements of the permutation.
[Solution] Decinc Dividing solution codeforces
Output the number of pairs of integers (𝑙,𝑟)(l,r) such that 𝑝[𝑙…𝑟]p[l…r] (the subarray of 𝑝p from 𝑙l to 𝑟r) is a Decinc array. (1≤𝑙≤𝑟≤𝑛)(1≤l≤r≤n)
3 2 3 1
6
6 4 5 2 6 1 3
[Solution] Decinc Dividing solution codeforces
19
10 7 10 1 8 3 9 2 4 6 5
39
In the first sample, all subarrays are Decinc.
In the second sample, all subarrays except 𝑝[1…6]p[1…6] and 𝑝[2…6]p[2…6] are Decinc.