CF1579E2 Array Optimization by Deque

实际上，问题 E1 和 E2 并没有太多共同之处。你应该将它们视为两个独立的问题。 给定一个整数数组 $a[1 \ldots n] = [a_1, a_2, \ldots, a_n]$。 我们考虑一个初始为空的 [双端队列（deque）](https://tinyurl.com/pfeucbux)。双端队列是一种支持在队首和队尾两端添加元素的数据结构。例如，当前队列中有元素 $[3, 4, 4]$，如果在队首添加元素 $1$，则队列变为 $[\color{red}{1}, 3, 4, 4]$；如果在队尾添加同样的元素，则队列变为 $[3, 4, 4, \color{red}{1}]$。 数组中的元素依次被加入到初始为空的双端队列中，从 $a_1$ 到 $a_n$。在每次将元素加入队列前，你可以选择将其加入队首或队尾。 例如，考虑数组 $a = [3, 7, 5, 5]$，其中一种可能的操作序列如下： $\quad$ 1. 将 $3$ 加入队首：队列为 $[\color{red}{3}]$； $\quad$ 2. 将 $7$ 加入队尾：队列为 $[3, \color{red}{7}]$； $\quad$ 3. 将 $5$ 加入队尾：队列为 $[3, 7, \color{red}{5}]$； $\quad$ 4. 将 $5$ 加入队首：队列为 $[\color{red}{5}, 3, 7, 5]$。 请你求出在整个数组处理完后，队列中可能的最小逆序对数。 在序列 $d$ 中，逆序对定义为一对下标 $(i, j)$，满足 $i < j$ 且 $d_i > d_j$。例如，数组 $d = [5, 3, 7, 5]$ 恰好有两个逆序对——$(1, 2)$ 和 $(3, 4)$，因为 $d_1 = 5 > 3 = d_2$ 且 $d_3 = 7 > 5 = d_4$。

第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。 接下来的 $2t$ 行描述每个测试用例。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示数组的长度。第二行包含 $n$ 个用空格分隔的整数 $a_i$（$-10^9 \le a_i \le 10^9$），表示数组的元素。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出 $t$ 行，每行一个整数，表示对应测试用例的答案，即经过上述操作后队列中可能的最小逆序对数。

在题目描述中，给出了一种将初始数组 $[3, 7, 5, 5]$ 变为队列 $[5, 3, 7, 5]$ 并且只包含两个逆序对的方法。 另外，在这个例子中，你也可以直接将原数组的每个元素都放在队尾，得到的队列 $[3, 7, 5, 5]$ 也恰好有两个逆序对。 由 ChatGPT 4.1 翻译