A16697 | $Inverse Minimum Partition (Hard Version)$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

这是该问题的困难版本。不同版本的区别在于，本版本要求你计算 $a$ 的所有连续子序列 $b$ 的 $f(b)$ 之和。只有在你解决了所有版本后，才能进行 Hack。 对于一段长度为 $k$ 的正整数序列 $b$，其“代价”定义如下$^*$： $$ \mathtt{cost}(b)=\left\lceil \frac{b_k}{\min(b_1,b_2,\ldots,b_k)} \right\rceil $$ 假设你将一个序列 $c$ 分割成一个或多个序列，使得这些序列拼接起来还是 $c$。例如，若序列 $c$ 为 $[3,1,4,1,5]$，那么如下几种分割方式都是合法的：$[[3,1],[4,1,5]]$、$[[3],[1,4,1],[5]]$、$[[3,1,4,1,5]]$。而 $[[3,1],[1,5]]$ 和 $[[3,4,1],[1,5]]$ 不是合法分割方式。 对于一个正整数序列 $c$ 的一个分割，其总代价定义为分割中每个序列的代价之和。我们定义 $f(c)$ 为将序列 $c$ 分割后的最小总代价。 给定一个长度为 $n$ 的正整数序列 $a$，你需要计算： $$ \sum_{l=1}^{n} \sum_{r=l}^{n} f([a_l,a_{l+1},\ldots,a_r]) $$ $^*$ 给定一个实数 $x$，$\lceil x\rceil$ 定义为不小于 $x$ 的最小整数。例如，$\lceil 3.14\rceil=4$。

每组测试数据包含多组测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 10^4$）。接下来是每组测试用例的描述。 每组测试用例第一行包含单个整数 $n$（$1 \le n \le 4 \cdot 10^5$）。 第二行包含 $a_1,a_2,\ldots,a_n$（$1 \le a_i \le 10^{18}$）。 保证所有测试用例中 $n$ 的总和不超过 $4 \cdot 10^5$。

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

输入 #1

4
5
3 1 4 1 5
10
9 2 6 5 3 5 8 9 7 9
8
1 2 3 4 5 6 7 8
2
1 1000000000000000000

输出 #1

C++ 编辑器

输入

输出