← 返回题目列表

Codeforces · 1579/E2

E2. 通过 Deque 进行数组优化

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

事实上,问题E1和E2并没有太多共同点。您可能应该将它们视为两个独立的问题。

给定一个整数数组 $$$a[1 \ldots n] = [a_1, a_2, \ldots, a_n]$$$。

让我们考虑一个空的双端队列(双端队列)。双端队列是一种支持在开头和结尾添加元素的数据结构。因此,如果双端队列中当前有元素 $$$[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.add $$$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$$$ 行,每行包含相应测试用例的答案。测试用例的答案应该是一个整数——执行所描述的算法后双端队列中可能的最小反转次数。

示例

输入 #1

6
4
3 7 5 5
3
3 2 1
3
3 1 2
4
-1 2 2 -1
4
4 5 1 3
5
1 3 1 3 2

输出 #1

2
0
1
0
1
2

注意

问题陈述中描述了从初始数组 $$$[3, 7, 5, 5]$$$ (第一个示例测试用例)获取双端队列中仅包含两个反转的序列 $$$[5, 3, 7, 5]$$$ 的方法之一。

另外,在这个例子中,只需将原始数组的每个元素放在双端队列的末尾,您就可以获得两次反转的答案。在这种情况下,原始序列 $$$[3, 7, 5, 5]$$$(也恰好包含两个反转)将按原样位于双端队列中。