CF1967F.Next and Prev

设 $p_1, \ldots, p_n$ 是 $[1, \ldots, n]$ 的一个排列。

$p$ 的 $q$-子序列是 $[1, q]$ 的一个排列，其元素在 $p_1, \ldots, p_n$ 中的相对顺序保持不变。也就是说，从 $p$ 中依次提取所有不超过 $q$ 的元素，按原顺序排列，这些元素组成 $p$ 的 $q$-子序列。

对于给定的数组 $a$，定义 $pre(i)$ 为满足 $pre(i) < i$ 且 $a_{pre(i)} > a_i$ 的最大值。如果不存在这样的 $pre(i)$，则令 $pre(i) = -10^{100}$。定义 $nxt(i)$ 为满足 $nxt(i) > i$ 且 $a_{nxt(i)} > a_i$ 的最小值。如果不存在这样的 $nxt(i)$，则令 $nxt(i) = 10^{100}$。

对于每个 $1 \leq q \leq n$，令 $a_1, \ldots, a_q$ 为 $p$ 的 $q$-子序列。对于每个 $1 \leq i \leq q$，按照上述定义计算 $pre(i)$ 和 $nxt(i)$。接下来，给定若干整数 $x$，对于每个 $x$，你需要计算 $\sum\limits_{i=1}^q \min(nxt(i) - pre(i), x)$。

每个测试点包含多组测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 3 \cdot 10^5$），表示排列的长度。

第二行包含 $n$ 个整数 $p_1, \ldots, p_n$（$1 \leq p_i \leq n$），表示初始排列。

接下来，对于每个 $1 \leq q \leq n$，按升序给出一个整数 $k$（$0 \leq k \leq 10^5$），表示针对 $q$-子序列的询问数量。随后一行包含 $k$ 个整数，分别表示每次询问的 $x$（$1 \leq x \leq q$）。

保证所有测试用例中 $n$ 的总和不超过 $3 \cdot 10^5$，所有测试用例中 $k$ 的总和不超过 $10^5$。

对于每个测试用例，对于每个询问，输出一行一个整数，表示该询问的答案。

$1$-子序列为 $[1]$，此时 $pre=[-10^{100}]$，$nxt=[10^{100}]$。$ans(1)=\min(10^{100}-(-10^{100}),1)=1$。

$5$-子序列为 $[1,4,3,2,5]$，此时 $pre=[-10^{100},-10^{100},2,3,-10^{100}]$，$nxt=[2,5,5,5,10^{100}]$。$ans(1)=5,ans(2)=10,ans(3)=14$。

由 ChatGPT 4.1 翻译