← 返回题目列表

Codeforces · 2241/G

G. 召唤

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

请注意,此问题的答案可能不适合 int64 或 long long。推荐使用int128。

对于任何长度为 $$$m$$$ 的数组 $$$b$$$,将 $$$f(b)$$$ 定义为 最小值 $$$\max(b) - \min(b)$$$ 的可能值可以通过执行以下操作任意次来实现:

  • 选择任何索引 $$$1 \le i \lt m$$$,并执行以下操作之一:
    1. 设置 $$$b_{i+1} := b_{i+1} + b_i$$$,
    2. 设置 $$$b_{i+1} := b_{i+1} - b_i$$$。

给你一个长度为 $$$n$$$ 的数组 $$$a$$$。您的任务是计算 $$$a$$$ 的所有子数组 $$$^{\text{∗}}$$$ 的 $$$f$$$ 之和。更正式地说,确定

$$\sum_{1 \le l \le r \le n} f([a_l,a_{l+1},\dots,a_r]).$$

$$$^{\text{*}}$$$ 数组 $$$b$$$ 是数组 $$$a$$$ 的子数组,如果 $$$b$$$ 可以通过从 $$$a$$$ 删除开头的几个(可能是零个或全部)元素和从末尾删除几个(可能是零个或全部)元素来获得。特别是,数组是其自身的子数组。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。每个测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$) — 数组 $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 数组 $$$a$$$ 的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot10^5$$$。

输出

对于每个测试用例,打印一个整数 - $$$\sum_{1 \le l \le r \le n} f([a_l,a_{l+1},\dots,a_r])$$$ 的值。

示例

输入
复制

5
3
6 4 8
4
1 2 3 4
9
9 9 8 2 4 4 3 5 3
6
18 12 24 9 6 36
6
36 24 18 12 9 6

输出
复制

4
3
39
72
111

注意

对于第一个测试用例,让我们看看所有子数组。

  • 对于单元素子数组 $$$[6]$$$、$$$[4]$$$ 和 $$$[8]$$$,任何操作都无法更改任何内容,因此它们每个都贡献 $$$0$$$。
  • 对于$$$[6,4]$$$,第一个元素固定为$$$6$$$。第二个元素只能更改为$$$4+6=10$$$ 或$$$4-6=-2$$$,因此间隙将变为$$$4$$$ 或$$$8$$$。因此,最好不做任何操作,贡献为$$$2$$$。
  • 对于 $$$[4,8]$$$,我们选择 $$$i=1$$$ 并应用 $$$b_{2}:=b_{2}-b_{1}$$$。那么子数组就变成了$$$[4,4]$$$,所以它的贡献就是$$$0$$$。
  • 对于$$$[6,4,8]$$$,我们保持前两个元素不变并选择$$$i=2$$$。然后我们应用 $$$b_{3}:=b_{3}-b_{2}$$$,因此 $$$8$$$ 变为 $$$4$$$。该数组变为$$$[6,4,4]$$$,因此$$$\max(b)-\min(b)=6-4=2$$$。可以证明这是最优值。

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

对于第二个测试用例,长度为 $$$1$$$ 的每个子数组贡献 $$$0$$$。其余子数组中,只有 $$$[2,3]$$$、$$$[3,4]$$$ 和 $$$[2,3,4]$$$ 具有非零贡献,每个子数组贡献 $$$1$$$。因此,答案是$$$1+1+1=3$$$。