A16751 | $Arctic Acquisition$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

给定一个长度为 $n$ 的排列 $a_1,a_2,\ldots,a_n$。 对于一个区间 $[l,r]$（$1\le l\le r\le n$），如果它包含一个 21435 子序列，则称其为一个“jagged”区间；也就是说，存在整数 $i_1,i_2,i_3,i_4,i_5$，使得 $l\le i_1<i_2<i_3<i_4<i_5\le r$，并且 $a_{i_2}<a_{i_1}<a_{i_4}<a_{i_3}<a_{i_5}$。 你的任务是计算在 $\frac{n(n+1)}{2}$ 个区间中，有多少个区间是 “jagged” 的。 附：排列指的是长度为 $n$ 的数组，包含 $1$ 到 $n$ 的 $n$ 个互不相同的整数，顺序任意。例如 $[2,3,1,5,4]$ 是一个排列，但是 $[1,2,2]$ 不是（$2$ 出现两次），$[1,3,4]$ 也不是（$n=3$，但数组中有 $4$）。

输入格式

每组测试包含若干个测试用例。第一行为测试用例的数量 $t$（$1 \le t \le 10^4$）。每组测试用例描述如下。 每组测试用例第一行包含一个整数 $n$（$1\le n\le10^6$），表示排列的长度。 第二行包含 $n$ 个互不相同的整数 $a_1,a_2,\ldots,a_n$（$1\le a_i\le n$）。 保证所有测试用例中 $n$ 的总和不超过 $10^6$。

输出格式

对于每组测试用例，输出 jagged 区间的个数。

输入输出样例

输入 #1

5
5
2 1 4 3 5
10
10 3 5 2 1 4 9 8 6 7
15
3 9 15 6 11 10 5 13 12 7 4 8 14 1 2
12
10 7 12 5 4 1 2 9 3 8 6 11
30
22 30 7 17 4 13 26 28 24 20 2 11 27 21 5 19 9 10 23 14 1 25 6 8 3 18 29 12 16 15

输出 #1

C++ 编辑器

输入

输出

A16751 | Arctic Acquisition

题目描述

输入格式

输出格式

输入输出样例

A16751 | $Arctic Acquisition$