题目详情题解（0）讨论（0）提交记录（0）

CFCF2159D2.Inverse Minimum Partition (Hard Version)

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

这是该问题的困难版本。不同版本的区别在于，本版本要求你计算 aa 的所有连续子序列 bb 的 f(b)f(b) 之和。只有在你解决了所有版本后，才能进行 Hack。

对于一段长度为 kk 的正整数序列 bb，其“代价”定义如下∗^*：

cost(b)=⌈bkmin⁡(b1,b2,…,bk)⌉\mathtt{cost}(b)=\left\lceil \frac{b_k}{\min(b_1,b_2,\ldots,b_k)} \right\rceil

假设你将一个序列 cc 分割成一个或多个序列，使得这些序列拼接起来还是 cc。例如，若序列 cc 为 [3,1,4,1,5][3,1,4,1,5]，那么如下几种分割方式都是合法的：[[3,1],[4,1,5]][[3,1],[4,1,5]]、[[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,1],[1,5]] 和 [[3,4,1],[1,5]][[3,4,1],[1,5]] 不是合法分割方式。

对于一个正整数序列 cc 的一个分割，其总代价定义为分割中每个序列的代价之和。我们定义 f(c)f(c) 为将序列 cc 分割后的最小总代价。

给定一个长度为 nn 的正整数序列 aa，你需要计算：

∑l=1n∑r=lnf([al,al+1,…,ar])\sum_{l=1}^{n} \sum_{r=l}^{n} f([a_l,a_{l+1},\ldots,a_r])

∗^* 给定一个实数 xx，⌈x⌉\lceil x\rceil 定义为不小于 xx 的最小整数。例如，⌈3.14⌉=4\lceil 3.14\rceil=4。

输入格式

每组测试数据包含多组测试用例。第一行包含测试用例数量 tt（1≤t≤1041 \le t \le 10^4）。接下来是每组测试用例的描述。

每组测试用例第一行包含单个整数 nn（1≤n≤4⋅1051 \le n \le 4 \cdot 10^5）。

第二行包含 a1,a2,…,ana_1,a_2,\ldots,a_n（1≤ai≤10181 \le a_i \le 10^{18}）。

保证所有测试用例中 nn 的总和不超过 4⋅1054 \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

    21
124
84
4

说明/提示

对于第一个测试用例，所有 aa 的连续子序列以及对应的值如下：

  • [3]→[[3]][3] \to [[3]]：f([3])=1f([3])=1；
  • [3,1]→[[3,1]][3,1] \to [[3,1]]：f([3,1])=1f([3,1])=1；
  • [3,1,4]→[[3,1],[4]][3,1,4] \to [[3,1],[4]]：f([3,1,4])=2f([3,1,4])=2；
  • [3,1,4,1]→[[3,1,4,1]][3,1,4,1] \to [[3,1,4,1]]：f([3,1,4,1])=1f([3,1,4,1])=1；
  • [3,1,4,1,5]→[[3,1,4,1],[5]][3,1,4,1,5] \to [[3,1,4,1],[5]]：f([3,1,4,1,5])=2f([3,1,4,1,5])=2；
  • [1]→[[1]][1] \to [[1]]：f([1])=1f([1])=1；
  • [1,4]→[[1],[4]][1,4] \to [[1],[4]]：f([1,4])=2f([1,4])=2；
  • [1,4,1]→[[1,4,1]][1,4,1] \to [[1,4,1]]：f([1,4,1])=1f([1,4,1])=1；
  • [1,4,1,5]→[[1,4,1],[5]][1,4,1,5] \to [[1,4,1],[5]]：f([1,4,1,5])=2f([1,4,1,5])=2；
  • [4]→[[4]][4] \to [[4]]：f([4])=1f([4])=1；
  • [4,1]→[[4,1]][4,1] \to [[4,1]]：f([4,1])=1f([4,1])=1；
  • [4,1,5]→[[4,1],[5]][4,1,5] \to [[4,1],[5]]：f([4,1,5])=2f([4,1,5])=2；
  • [1]→[[1]][1] \to [[1]]：f([1])=1f([1])=1；
  • [1,5]→[[1],[5]][1,5] \to [[1],[5]]：f([1,5])=2f([1,5])=2；
  • [5]→[[5]][5] \to [[5]]：f([5])=1f([5])=1。

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

首页