对于要打印的 \(B\)，我们首先尝试确定 \(B_1\)。
让 \(f(x) (1≤x≤M)\) 是最大的 \(i\)，使 \(A_i = x\)。
对于 \(r:=\underset{{{1≤x≤M}}}{\min}f(x)\)，我们可以证明 \(B_1\) 是 \(A_1 ,A_2 ,...,A_r\) 中的一个（否则，\(B\) 是 \(A_{>r} :=(A_r+1 ,Ar+2,...,A_N)\)的一个子序列，但 \(A_{>r}\) 不包含 \(A_r\)，这违反了 \(B\) 的条件）。
相反，存在一个长度为 \(M\) 的子序列，其第一个元素是 \(A_i\) 中的一个 \((1≤i≤r)\)，它分别包含 \(1，2，...，M\) 一次。特别是，所有 \(A_{f(x)}\) 的子序列的 \(x\) 都有 \(x \neq A_i\)。
因此，\(B_1 =A_l = \underset{1≤i≤r}{\min}A_i\)。我们可以让 \(l\) 是最小的整数 \(j\)，使\(A_j=\underset{1≤i≤r}{\min}A_i\)。
我们可以通过对以下序列重复类似的问题来确定\(B\)的所有元素（对元素进行适当的替换）：
从 \(A\) 中除去前 \(l\) 项和所有使 \(A_i =B_1\) 的元素而得到的序列。
对一个序列的操作可以用一个优先级队列或一个段树来模拟。
在使用优先级队列管理 \((A_i ,i)\) 的情况下,我们可以通过把前r个词放在一起并找到它们的最小值来找到前 \(r\) 个元素的最小值。
移除 \(A\) 的前 \(l\) 个元素，并移除与某物相同的 \(A_i\)，可以通过重复从优先级队列中移除一个元素来实现，只要队列中的顶级元素满足一个条件。
在段树的情况下，我们也可以做类似的事情。
移除与某事物具有相同价值的 \(A_i\)，可以通过替换该 \(A_i\) 来实现。 删除时用 \(∞\) 来实现。
替换后，前 \(r\) 个元素的最小值是一个分段最小值。
这两种方法的时间复杂度都是 \(O(N\log{N})\)，足够快。
- Beginner Atcoder Contest 299beginner atcoder contest 299 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 310