← 返回题目列表

Codeforces · 2159/D2

D2. 逆最小分区(硬版)

中文机器翻译题面 查看原题

这是问题的困难版本。版本之间的差异在于,在此版本中,要求您计算 $$$a$$$ 的所有连续子序列 $$$b$$$ 上的 $$$f(b)$$$ 之和。只有解决了该问题的所有版本,您才能破解。

对于$$$k$$$正整数的某些序列$$$b$$$,该序列的成本定义如下$$$^{\text{*}}$$$:

$$\mathtt{成本}(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$$$ 的最小总成本。

给定 $$$a$$$ 的 $$$n$$$ 正整数序列,您必须计算以下内容:

$$\sum_{l=1}^{n} {\sum_{r=l}^{n} f([a_l,a_{l+1},\ldots,a_r])}$$

$$$^{\text{*}}$$$给定一个实值$$$x$$$,$$$\left\lceil{x}\right\rceil$$$被定义为不小于$$$x$$$的最小整数。例如,$$$\left\lceil{3.14}\right\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$$$。

输出

对于每个测试用例,在单独的行上输出问题的答案。

示例

输入
复制

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

输出
复制

21
124
84
4

注意

对于第一个测试用例,以下是 $$$a$$$ 的所有连续子序列及其对应的值:

  • $$$[3] \到 [[3]]$$$: $$$f([3])=1$$$;
  • $$$[3,1] \到 [[3,1]]$$$: $$$f([3,1])=1$$$;
  • $$$[3,1,4] \到 [[3,1],[4]]$$$: $$$f([3,1,4])=2$$$;
  • $$$[3,1,4,1] \到 [[3,1,4,1]]$$$: $$$f([3,1,4,1])=1$$$;
  • $$$[3,1,4,1,5] \到 [[3,1,4,1],[5]]$$$: $$$f([3,1,4,1,5])=2$$$;
  • $$$[1] \到 [[1]]$$$: $$$f([1])=1$$$;
  • $$$[1,4] \到 [[1],[4]]$$$: $$$f([1,4])=2$$$;
  • $$$[1,4,1] \到 [[1,4,1]]$$$: $$$f([1,4,1])=1$$$;
  • $$$[1,4,1,5] \到 [[1,4,1],[5]]$$$: $$$f([1,4,1,5])=2$$$;
  • $$$[4] \到 [[4]]$$$: $$$f([4])=1$$$;
  • $$$[4,1] \到 [[4,1]]$$$: $$$f([4,1])=1$$$;
  • $$$[4,1,5] \到 [[4,1],[5]]$$$: $$$f([4,1,5])=2$$$;
  • $$$[1] \到 [[1]]$$$: $$$f([1])=1$$$;
  • $$$[1,5] \到 [[1],[5]]$$$: $$$f([1,5])=2$$$;
  • $$$[5] \ 到 [[5]]$$$: $$$f([5])=1$$$。

因此,第一个测试用例的答案是$$$1+1+2+1+2+1+2+1+2+1+1+2+1+2+1=21$$$。