CF1827B2 Range Sorting (Hard Version)

本题与简单版本的唯一区别在于 $t$ 和 $n$ 的约束条件。 给定一个由 $n$ 个互不相同的整数 $a_1, a_2, \ldots, a_n$ 组成的数组 $a$。 定义一个数组 $p_1, p_2, \ldots, p_k$ 的“美丽值”为使用任意次数的区间排序操作将该数组排序所需的最少时间。每次区间排序操作，你可以进行如下操作： - 选择两个整数 $l$ 和 $r$（$1 \le l < r \le k$）。 - 将子数组 $p_l, p_{l + 1}, \ldots, p_r$ 排序，耗时为 $r - l$ 秒。 请计算数组 $a$ 的所有子数组的美丽值之和。 一个数组的子数组定义为该数组中一段连续的元素序列。

每组测试包含多个测试用例。第一行为测试用例数 $t$（$1 \le t \le 10^4$）。接下来是每个测试用例的描述。 每个测试用例的第一行为一个整数 $n$（$1 \le n \le 3 \cdot 10^5$），表示数组 $a$ 的长度。 第二行为 $n$ 个整数 $a_1,a_2,\ldots, a_n$（$1\le a_i\le 10^9$）。保证所有 $a$ 中的元素两两不同。 保证所有测试用例中 $n$ 的总和不超过 $3 \cdot 10^5$。

对于每个测试用例，输出数组 $a$ 所有子数组的美丽值之和。

在第一个测试用例中： - 子数组 $[6]$ 已经有序，所以美丽值为 $0$。 - 子数组 $[4]$ 已经有序，所以美丽值为 $0$。 - 你可以通过选择 $l = 1$ 和 $r = 2$，一次操作将子数组 $[6, 4]$ 排序。其美丽值为 $1$。 给定数组所有子数组的美丽值之和为 $0 + 0 + 1 = 1$。 在第二个测试用例中： - 子数组 $[3]$ 已经有序，所以美丽值为 $0$。 - 子数组 $[10]$ 已经有序，所以美丽值为 $0$。 - 子数组 $[6]$ 已经有序，所以美丽值为 $0$。 - 子数组 $[3, 10]$ 已经有序，所以美丽值为 $0$。 - 你可以通过选择 $l = 1$ 和 $r = 2$，一次操作将子数组 $[10, 6]$ 排序。其美丽值为 $2 - 1 = 1$。 - 你可以通过选择 $l = 2$ 和 $r = 3$，一次操作将子数组 $[3, 10, 6]$ 排序。其美丽值为 $3 - 2 = 1$。 给定数组所有子数组的美丽值之和为 $0 + 0 + 0 + 0 + 1 + 1 = 2$。 由 ChatGPT 4.1 翻译