---

 题目描述：

　　有两个栈A和B，以及四种操作：元素入栈A称为操作a，元素出栈A称为操作b，元素入栈B称为操作c，元素出栈B称为操作d。现在有一个长度为n(1≤N≤1000)的全排列序列，要求通过两个栈，输出1..N的序列，问能否达成，若能，则要求输出字典序最少的方案。

思考&分析：

　　  拿到这个题第一反应是：爆搜？时间复杂度(2^1000)^2=4^1000=1.148e+602……

　　先把问题简化下，如果单栈怎么搞？

　　你会发现单栈很好做：如果当前的要入栈的元素已经到了输出的时候，赶紧压进去然后输出来；否则你就先存在那儿，等它到了输出的时候看它是不是在栈顶，如果是把它输出来，否则就是不行。

　　然后你会发现这个道理在双栈根本行不通。

　　仍然考虑单栈，换个角度思考下，什么样的情况在单栈会挂掉？

　　容易发现：当出现这样的序列时，单栈会挂掉：a[k]<a[i]<a[j]&&i<j<k。

　　如果你有双栈，这样是不会挂的，你可以先把a[i]暂存在A栈，把a[j]暂存在B栈，然后问题就解决了。

　　在双栈中，如果出现这样的序列，a[i]和a[j]必须存在不同的栈中，否则会挂掉。

　　所以先要把这些i,j全部找出来，朴素找是O(N^3)的，会T，然而一个小小的后缀Min优化就可以是复杂度降为O(N^2)。

　　找出来以后，你发现这是一个并查集裸题，开两倍数组，用i+n来表示i的对立面，对于必须存在不同栈中的i和j。

　　i和j+n要合并到同一集合，j和i+n要合并到同一集合，但是如果你发现i和j或是i+n和j+n合并到同一集合去了，那么说明：出问题了。

　　如果做完之后都没发现问题，那么你可以确定每个数要到A栈还是B栈（如果都可以去优先A栈）。

　　依次模拟一下即可，按顺序入栈，发现能出栈就出栈。

　　然后你就能A掉此题。

贴代码：

#include 
     
      using namespace std;const int maxn=1005;int n,a[maxn],Min[maxn],f[maxn*2],bh[maxn*2];int t1,t2,st1[maxn],st2[maxn];int getfather(int x){    if (f[x]==x) return x; else f[x]=getfather(f[x]);    return f[x];}int main(){    scanf("%d",&n);    for (int i=1;i<=n;i++) scanf("%d",&a[i]);    Min[n]=a[n];    for (int i=n-1;i>=1;i--)        Min[i]=min(Min[i+1],a[i]);    for (int i=1;i<=2*n;i++) f[i]=i;    bool flag=true;    int fa,fb,fc,fd;    for (int i=1;i