CF2201A2 Lost Civilization (Hard Version)

这是本题的困难版本。不同之处在于，在这个版本中，你必须计算所有子区间的值的总和。只有当你解决了本题的所有版本时才可以进行 Hack。 我们定义生成 $m+k$ 个整数序列的算法如下： 1. 首先，输入一个长度为 $m$ 的整数序列 $x$。如果 $k=0$，立即终止并返回序列 $x$。 2. 然后，选择任意一个下标 $1 \le i \le |x|$，并在 $x_i$ 之后插入一个值为 $x_i+1$ 的元素。 3. 如果 $x$ 恰好包含 $m+k$ 个整数，终止并返回序列 $x$。否则，返回执行第二步。 Alice 知道远古文明曾用这种算法来安全地隐藏他们的秘密。Alice 很想知道他们藏的知识，但根据输出推测输入并不容易。 对于长度为 $n$ 的整数序列 $b$，我们定义 $f(b)$ 为能够作为该算法输入生成 $b$ 的最短序列的长度。 给定一个长度为 $n$ 的整数序列 $a$，请计算如下的和： $$ \sum_{l=1}^n {\sum_{r=l}^n {f([a_l,a_{l+1},\ldots,a_r])}} $$ 也就是说，你需要计算 $a$ 的所有子区间 $c$ 的 $f(c)$ 之和。 $^{\text{∗}}$ 序列 $a$ 是序列 $b$ 的子区间，指从 $b$ 中仅删去若干（可以为零或全部）开头和若干（可以为零或全部）结尾的元素即可得到 $a$。若删除元素的位置不同，两个子区间视为不同。

每个测试点包含多组测试数据。第一行为测试用例数 $t$（$1 \le t \le 10^4$）。 接下来是每组测试数据描述。 每组测试数据的第一行为一个整数 $n$（$1 \le n \le 300\,000$）。 第二行为 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1 \le a_i \le 10^9$）。 保证所有测试用例中 $n$ 之和不超过 $300\,000$。

每个测试用例输出一行答案。

对于第一个测试用例，$a=[1,2,3,4,5]$ 的所有子区间都可以由长度为 $1$ 的序列生成。 对于第二个测试用例，$a=[1,3,5,7,9]$ 的所有子区间都无法由比自身更短的序列生成。 由 ChatGPT 5 翻译