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]$ 之外的所有子段都是好的。
定义一个序列 $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]$ 之外的所有子段都是好的。