309525: CF1693D. Decinc Dividing

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Decinc Dividing

题意翻译

### 题目描述 定义一个序列 $a$ 是好的,仅当可以通过删除 $a$ 的一个单调递减子序列(可以为空)使得 $a$ 单调递增。 给定一个 $1\sim n$ 的排列 $p$,你需要求出 $p$ 有多少子段是好的。 ### 输入格式 第一行输入一个整数 $n(1\leq n\leq2\times10^5)$。 接下来一行输入 $n$ 个整数 $p_1,p_2,\cdots,p_n(1\leq p_i\leq n)$,保证 $p_i$ 互不相同。 ### 输出格式 输出一行一个整数表示好的子段个数。 ### 样例解释 对于样例一,所有 $p$ 的子段都是好的。 对于样例二: - 例如 $p[1,5]$ 是好的,因为 $\{4,5,2,6,1\}$ 可以通过删除单调递减子序列 $\{4,2,1\}$ 得到一个单调递增序列 $\{5,6\}$。 - 事实上,除了 $p[1,6],p[2,6]$ 之外的所有子段都是好的。

题目描述

Let's call an array $ a $ of $ m $ integers $ a_1, a_2, \ldots, a_m $ Decinc if $ a $ can be made increasing by removing a decreasing subsequence (possibly empty) from it. - For example, if $ a = [3, 2, 4, 1, 5] $ , we can remove the decreasing subsequence $ [a_1, a_4] $ from $ a $ and obtain $ a = [2, 4, 5] $ , which is increasing. You are given a permutation $ p $ of numbers from $ 1 $ to $ n $ . Find the number of pairs of integers $ (l, r) $ with $ 1 \le l \le r \le n $ such that $ p[l \ldots r] $ (the subarray of $ p $ from $ l $ to $ r $ ) is a Decinc array.

输入输出格式

输入格式


The first line contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the size of $ p $ . The second line contains $ n $ integers $ p_1, p_2, \ldots, p_n $ ( $ 1 \le p_i \le n $ , all $ p_i $ are distinct) — elements of the permutation.

输出格式


Output the number of pairs of integers $ (l, r) $ such that $ p[l \ldots r] $ (the subarray of $ p $ from $ l $ to $ r $ ) is a Decinc array. $ (1 \le l \le r \le n) $

输入输出样例

输入样例 #1

3
2 3 1

输出样例 #1

6

输入样例 #2

6
4 5 2 6 1 3

输出样例 #2

19

输入样例 #3

10
7 10 1 8 3 9 2 4 6 5

输出样例 #3

39

说明

In the first sample, all subarrays are Decinc. In the second sample, all subarrays except $ p[1 \ldots 6] $ and $ p[2 \ldots 6] $ are Decinc.

Input

题意翻译

### 题目描述 定义一个序列 $a$ 是好的,仅当可以通过删除 $a$ 的一个单调递减子序列(可以为空)使得 $a$ 单调递增。 给定一个 $1\sim n$ 的排列 $p$,你需要求出 $p$ 有多少子段是好的。 ### 输入格式 第一行输入一个整数 $n(1\leq n\leq2\times10^5)$。 接下来一行输入 $n$ 个整数 $p_1,p_2,\cdots,p_n(1\leq p_i\leq n)$,保证 $p_i$ 互不相同。 ### 输出格式 输出一行一个整数表示好的子段个数。 ### 样例解释 对于样例一,所有 $p$ 的子段都是好的。 对于样例二: - 例如 $p[1,5]$ 是好的,因为 $\{4,5,2,6,1\}$ 可以通过删除单调递减子序列 $\{4,2,1\}$ 得到一个单调递增序列 $\{5,6\}$。 - 事实上,除了 $p[1,6],p[2,6]$ 之外的所有子段都是好的。

Output

**题意翻译**

定义一个序列 $a$ 是好的,仅当可以通过删除 $a$ 的一个单调递减子序列(可以为空)使得 $a$ 单调递增。
给定一个 $1\sim n$ 的排列 $p$,你需要求出 $p$ 有多少子段是好的。

**输入格式**

第一行输入一个整数 $n(1\leq n\leq2\times10^5)$。
接下来一行输入 $n$ 个整数 $p_1,p_2,\cdots,p_n(1\leq p_i\leq n)$,保证 $p_i$ 互不相同。

**输出格式**

输出一行一个整数表示好的子段个数。

**样例解释**

对于样例一,所有 $p$ 的子段都是好的。
对于样例二:

- 例如 $p[1,5]$ 是好的,因为 $\{4,5,2,6,1\}$ 可以通过删除单调递减子序列 $\{4,2,1\}$ 得到一个单调递增序列 $\{5,6\}$。
- 事实上,除了 $p[1,6],p[2,6]$ 之外的所有子段都是好的。**题意翻译** 定义一个序列 $a$ 是好的,仅当可以通过删除 $a$ 的一个单调递减子序列(可以为空)使得 $a$ 单调递增。 给定一个 $1\sim n$ 的排列 $p$,你需要求出 $p$ 有多少子段是好的。 **输入格式** 第一行输入一个整数 $n(1\leq n\leq2\times10^5)$。 接下来一行输入 $n$ 个整数 $p_1,p_2,\cdots,p_n(1\leq p_i\leq n)$,保证 $p_i$ 互不相同。 **输出格式** 输出一行一个整数表示好的子段个数。 **样例解释** 对于样例一,所有 $p$ 的子段都是好的。 对于样例二: - 例如 $p[1,5]$ 是好的,因为 $\{4,5,2,6,1\}$ 可以通过删除单调递减子序列 $\{4,2,1\}$ 得到一个单调递增序列 $\{5,6\}$。 - 事实上,除了 $p[1,6],p[2,6]$ 之外的所有子段都是好的。

加入题单

上一题 下一题 算法标签: