题目理解

我们有一个序列 $a_1, a_2, \dots, a_n$，要找一个最长的不含重复元素的子序列 $b$。
如果有多个最长的，选择将奇数位置上的元素乘 $-1$ 后字典序最小的那个。

子任务：忽略字典序最小，只求长度

显然，最长的无重复子序列的长度 $k$ 就是 $a$ 中不同元素的个数。
因为每个元素最多选一次，而我们可以把每个不同元素都选上（按某种顺序）。

所以：

构造 $b$ 从左到右，不破坏最长性

我们已知最大长度是 $k$，现在要构造 $b_1, b_2, \dots, b_k$，使得它是最优的（奇数位置乘 $-1$ 后字典序最小）。

假设我们已经选好了 $b_1, b_2, \dots, b_j$，其中 $b_j = a_i$（即最后一个选的是位置 $i$ 的值）。
我们要选 $b_{j+1}$，必须保证后面还能选出 $k - j$ 个不同的元素（包括 $b_{j+1}$ 本身）。

关键观察

设 $last_x$ 表示元素 $x$ 在子数组 $a[i+1, n]$ 中最后一次出现的位置，如果不存在则 $last_x = \infty$。

那么，我们可以在区间：

中任意选择一个位置作为 $b_{j+1}$ 的位置。
因为如果选的位置超过 $\min last_x$，那么某个元素 $x$ 就再也没有机会出现了，导致无法凑齐 $k - j$ 个不同元素。

如何最小化字典序（考虑奇数位置乘 $-1$）

我们要比较的是：

所以：

• 当 $j+1$ 是奇数时，我们希望 $b_{j+1}$ 尽可能小（因为乘 $-1$ 后负得更多，字典序更小）。
• 当 $j+1$ 是偶数时，我们希望 $b_{j+1}$ 尽可能大。

如果候选区间中有多个相同的最优值，我们选最左边的那个，因为这样剩下的后缀更长，更有利于后续构造。

窗口单调性

随着 $i$ 向右移动（即我们选的位置越来越靠后），候选区间的左边界 $i+1$ 递增，右边界 $\min last_x$ 也非递减（因为 $last_x$ 只会变小或不变，所以最小值不会变小）。

因此我们可以用优先队列（堆）或有序集合来维护候选元素。

算法步骤

1. 预处理每个值 $x$ 在 $a$ 中所有出现的位置（或最后一次出现）。
2. 初始化当前指针 $i = 0$（表示已选到位置 $i$）。
3. 对于 $j$ 从 $1$ 到 $k$：
   • 确定候选区间 $[i+1,\ R]$，其中 $R = \min_{x} last_x$，$last_x$ 是 $x$ 在 $a[i+1, n]$ 中的最后一次出现。
   • 如果 $j$ 是奇数：在区间内选最小的值；如果 $j$ 是偶数：选最大的值。若有多个相同值，选最左边的。
   • 设选中的位置是 $p$，值 $b_j = a_p$。
   • 更新 $i = p$，并删除 $b_j$ 的后续出现记录（因为它已被选过，不能再选）。
4. 输出 $b$。

时间复杂度

• 每个元素最多入堆/出堆一次。
• 使用优先队列维护最小值和最大值，$O(n \log n)$。
• 总和 $n \le 3\times 10^5$，可以通过。