BZOJ #3353. [IOI2009] Archery

这是一篇大概和题解不一样的做法。

首先一个平凡的转化是将我们要操作的这个数看作 \(0\) ，大于这个数的看作 \(1\) ，小于的看作 \(-1\) ，则原来的 \(2n\) 个数转化成对 \(3\) 种数的操作。

将这个序列两个数看作一组，并每组内分为上下两端。第一组规定小的在底下，大的在上面，其余的组大的在底下，小的在上面。

每次操作相当于将上面的序列循环转一圈，然后看有没有不满足上述规定的，如果有就调整。

这也就说明了至多 \(2n\) 步之后上下没有交换：一个 \(0\) 最多在下面 \(n\) 步就会被一个 \(1\) 换上来，然后再 \(n\) 步绕一圈找到一个 \(-1\) 换下去。

考虑这个操作的本质，相当于每个在上面的 \(1/0\)，不断前移直到下面为 \(0/-1\)，然后交换，也就是说，每个 \(0/1\) 找到最近的一个 \(0/-1\)，然后在换到的时候交换。

你会发现在 换到的时候 再交换非常不好。可不可以让它们在开始的时候就交换呢？

答案是可以的，交换完了之后序列都一样了没啥问题，交换之前因为一个在上面的 \(-1\) 不能换到底下去，在上面的 \(0\) 找不到更近的换到下面去，因此在开始的时候就交换是可以的。

我们将 \(2n\) 步之后序列相同的初始状态称为等价状态，我们要做的就是找到一个序列的等价状态中上下一直没有交换的一个。

这可以通过不断交换上面的数和下面的数来实现，设第 \(i\) 位置上面的数为 \(U_i\)，下面的为 \(D_i\)。我们分成三类讨论：

1. \(1<x<y\)，\(U_y>D_x\)，则要满足 \(x\) 是 \(y\) 最近的满足条件的位置，就会交换 \(U_y,D_x\)。
2. \(1=x<y,U_y<D_x\)，则要满足 \(y\) 是第一个上面的 \(0/-1\)，注意如果 \(0\) 被换下去了可能再被换一次。
3. \(x>y\)，\(U_y>D_x\)。这种情况需要第一种情况换完之后仍然剩下的点才能交换，且 \(x\) 是 \(y\) 从后往前走的第一个合法位置。

容易发现操作都可以用栈维护，因此可以做到 \(O(n)\) 算单个序列的答案。

记插入的这个数通过第三种状态交换到序列末尾的 真实位置 为在序列中的位置减去 \(n\)， 否则真实位置就是本身。观察发现，将第一个数插入序列中的位置越靠后，其真实位置应该更靠后。

我们要求的就是真实位置加某个常数模 \(n\) 的最小值，真实位置的值域显然在 \([-n,n]\) 之间，则可以分成 \(O(1)\) 段，每段内可以直接算最小值。都可以二分实现。时间复杂度 \(O(n\log n)\)。