A16490 | $Exquisite Array$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

称一个数字数组是 $k$ -精致的，如果它至少包含两个元素，并且任意两个相邻的数字之差至少为 $k$。 给定一个长度为 $n$ 的排列 $^{\text{∗}}$ $p$。对于每个 $k$ 从 $1$ 到 $n-1$，求出 $k$ -精致子数组的数量 $^{\text{†}}$。 $^{\text{∗}}$ 一个长度为 $n$ 的排列是一个包含从 $1$ 到 $n$ 的每个整数恰好一次的数组，顺序任意。 $^{\text{†}}$ 一个数组的子数组是指数组中一个或多个连续元素组成的序列。

第一行包含整数 $t$（$1 \le t \le 25000$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$，表示排列的长度（$2 \le n \le 10^5$）。 每个测试用例的第二行包含 $n$ 个整数 $p_i$，表示排列的元素（$1 \le p_i \le n$）。保证 $p_i$ 互不相同。 保证所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。

对于每个测试用例，输出所有 $k$ 从 $1$ 到 $n-1$ 的 $k$ -精致子数组的数量。

输入 #1

输出 #1

10 6 3 1 
3 0 
6 2 0

C++ 编辑器

输入

输出