CF1988E Range Minimum Sum

题目描述

对于一个长度为 $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。 $$

一个排列是长度为 $n$ 的整数序列，包含 $1$ 到 $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$ 后 $f(b)$ 的值。

输入输出样例 #1

输入 #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$。

由 ChatGPT 4.1 翻译