ACL Contest 1 F - Center Rearranging
退役选手来翻译题解了
首先B由A操作而来，B一定有连续一段是没被动过的，将它们称为M；M左边都被被动过，且最后一次被用了一个push_front操作，称为L；M右边最后一次操作是push_back，称为R
(Lcdots LMcdots MRcdots R)构成一个B的来源序列，显然只有(O(n^2))种，先枚举它，之后这个序列就确定了
考虑B中的一种数(有3个)。A中也有3个这种数。从A,B中单独抽出这些数，考虑他们是怎么匹配的。
先考虑B中这3个数(位置从小到大)的来源，共有10种序列，其中(LLL,RRR)显然是不可能的，剩下8种可能情况。经过艰苦卓绝的手算可以发现，除了(LMR)之外，所有M的来源位置其实是确定的，如下表
第1组
M** ***
LMR LLR
第2组
**M ***
LMR LRR
---
M** **M
MRR LLM
MMM
MMM
M*M M*M
LMM MMR
确定M来源位置的用处是用于答案可行性的判定。对于所有(M)，在A中原位置和B中新位置连一条边，显然这些边不能相交。（注意(M)不会被操作）
而(LMR)的M的来源位置也只有两种可能，现在暂且先确定每个(LMR)的M来源位置。
对于上面的表，先考虑一个简单的情况：如果(B)只有下面3组时怎么求解最小步数，可以发现，最小步数就是3n-M的数量，这显然也是下界。因为可以直接根据B中的位置来做所有L,R操作到达B的状态。
考虑加上1,2组之后怎么构造方案。1,2组有一个特点，就是不能乱做操作。比如第一组中的LMR，它只能是先做push_back再做push_front，也就是R的生成时间一定得比L更早。LLR也是，由于最右边的那个最后一次操作不可能是push_front，所以R的生成时间一定得比第一个L早。（当然了，第二个L的生成时间也得比第一个L早）第2组同理，L的生成时间必须比最后一个R早。
对于第1组，在B上第3个位置向第1个位置连一条边；对于第2组，在B上第1个位置向第3个位置连一条边，代表B中一个元素必须比另一个先生成。B上还存在一些边，就是右边的L元素向左边的L连边，左边的R向右边的R连边。这些所有边构成一个拓扑图，可以感性理解不存在其它限制（雾）。如果没有环就可以按照拓扑序做操作，完美还原序列。
怎么判环呢？可以发现，如果这个图存在环，一定可以抽出这样的环：一个第1组的第1,3位置都比一个第2组的1,3位置更小。这样的话判环就转化成了判一个二元关系。
还有一个限制“M连的边不相交”其实也是一个二元关系。
注意(LMR)的类型还没确定，不过只有两种情况可以用2sat求解。因为限制都是二元关系所以就很好做了。