← 返回题目列表

Codeforces · 1988/E

E. 范围最小总和

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

对于长度为 $$$n$$$ 的数组 $$$[a_1,a_2,\ldots,a_n]$$$,将 $$$f(a)$$$ 定义为所有子段的最小元素之和。即 $$$$$$f(a)=\sum_{l=1}^n\sum_{r=l}^n \min_{l\le i\le r}a_i.$$$$$$

排列是从 $$$1$$$ 到 $$$n$$$ 的整数序列,长度为 $$$n$$$,每个数字恰好包含一次。给你一个排列 $$$[a_1,a_2,\ldots,a_n]$$$。对于每个 $$$i$$$,独立解决以下问题:

- 从 $$$a$$$ 中删除 $$$a_i$$$,连接剩余部分,得到 $$$b = [a_1,a_2,\ldots,a_{i-1},\;a_{i+1},\ldots,a_{n}]$$$。
- 计算$$$f(b)$$$。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n\le 5\cdot 10^5$$$)。

每个测试用例的第二行包含 $$$n$$$ 不同的整数 $$$a_1,\ldots,a_n$$$ ($$$1\le a_i\le n$$$)。

保证所有测试用例的$$$n$$$总和不超过$$$10^6$$$。

输出

对于每个测试用例,打印一行包含 $$$n$$$ 整数。第 $$$i$$$ 个整数应该是擦除 $$$a_i$$$ 时的答案。

示例

输入 #1

4
1
1
3
3 1 2
5
4 2 1 5 3
8
8 1 4 6 7 3 5 2

输出 #1

0 
4 7 5 
19 21 27 17 19 
79 100 72 68 67 80 73 80

注意

在第二个测试用例中,$$$a=[3,1,2]$$$。

- 删除 $$$a_1$$$ 时,$$$b=[1,2]$$$。 $$$f(b)=1+2+\min\{1,2\}=4$$$。
- 删除 $$$a_2$$$ 时,$$$b=[3,2]$$$。 $$$f(b)=3+2+\min\{3,2\}=7$$$。
- 删除 $$$a_3$$$ 时,$$$b=[3,1]$$$。 $$$f(b)=3+1+\min\{3,1\}=5$$$。