题意

有 $2n$ 个数字排成一列，每个数字 $1\sim n$ 恰好出现两次。两种操作：

1. 交换相邻两个数字（代价 $1$）；
2. 若两个相同数字相邻，将它们移除（代价 $1$），剩余数字靠拢。

求把所有数字对都移除的最少操作次数。

思路

核心观察：每对数字最终都要被"移除"，共 $n$ 次移除操作。额外的代价来自"交换"——当一对相同数字不相邻时，需要先把它们之间的数字处理掉（通过它们各自的移除或交换）。

具体地，从左到右扫描：

• 遇到数字 $x$ 的第一次出现：记录位置。
• 遇到数字 $x$ 的第二次出现：此时它第一次出现位置 $f_x$ 和当前位置之间，若还夹着 $k$ 个"尚未配对"的数字，则这些数字必须在 $x$ 被移除前先被处理，因此会产生 $k$ 次额外的"交换/移除"代价。

答案 = $n + \sum k$，其中 $k$ 是每对数字第二次出现时，两次出现之间尚未配对的数字数量。

用树状数组维护"尚未配对"的数字：第一次出现时在对应位置 $+1$，第二次出现时查询区间和得到 $k$，并把第一次出现的位置 $-1$。

复杂度

$O(n\log n)$。