A16751. Arctic Acquisition
编程题
NOI/NOI+/CTSC
知识点
题目描述
给定一个长度为 $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$）。
对于一个区间 $[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$。
每组测试用例第一行包含一个整数 $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
1 0 28 5 185
说明/提示
在第一个测试用例中，唯一的 jagged 区间是 $[1,5]$，因为它包含 $[2,1,4,3,5]$ 作为子序列。
在第三个测试用例中，区间 $[1,8]$ 是 jagged 的，因为它包含 $[9,6,11,10,13]$ 作为子序列，这就是一个 21435-子序列。
在第三个测试用例中，区间 $[1,8]$ 是 jagged 的，因为它包含 $[9,6,11,10,13]$ 作为子序列，这就是一个 21435-子序列。