真是一道毒瘤题。

如果你想要让代码可读性更强，让思路显示更清晰，可以参考鄙人的写法。

分析

Part 1

对于一个栈来说，若对于可排序列，其出栈顺序为升序，则栈中元素必定时刻保持降序（若出现特例，则考虑出栈）。

即，如果只有一个栈，则整个操作顺序是固定的：

• 从前往后遍历每个数，每次先将当前数压入栈中，如果后面的所有数均比栈顶元素大，则将栈顶弹出，否则栈顶不能被弹出。

进一步分析，将该性质移用到双栈上。

• 性质1：$a_i$，$a_j$ 不归属于同一个栈，等价于：$\exists i<j<k$，使得 $a_k<a_i<a_j$。

这是一个很强的性质，以下为简述证明：

• 必要性：若存在这样的 $k$，则使得 $a_k$ 一定比 $a_i$，$a_j$ 先出栈，即在对 $a_k$ 操作前，$a_i$，$a_j$ 都不能弹出，否则出栈序列中将出现逆序对。这导致 $a_i$，$a_j$ 同时 在栈中。此时不论如何出栈都会出现逆序对，不合题意，故 $a_i$，$a_j$ 不归属于同一个栈。

• 充分性：可以转化为以下问题：若不存在这样的 $k$，$a_i$，$a_j$ 可以归属于同一个栈。这是显然的，因为为了保证栈的单调性，所有小于 $a_j$ 的数已经出栈了（后面没有更小的数了，因此可以正常出栈）；所有大于 $a_j$ 的数仍在栈底处。操作可以正确进行。

Part 2

这一部分主要是讲解输出时字典序最小的问题，有点绕。 得到了上一部分的性质，则能得到每个数之间的关系，要将它们分到两个栈中，正是二分图判定问题。跑一遍染色法求解二分图即可。注意从此开始与字典序有关，尽可能先进 stk1，染色时优先染 $0$（$0$ 是在 stk1 中的标志）。

之后出栈判断可以概括为：要出 stk1 就出，尽可能晚出 stk2 的元素。详细步骤如下：

1. 对于 $col=0$ 的元素，即要入 stk1 的元素，先对 stk1 进行检索、弹出（因为要进栈了，保证单调性）。然后如果此时 stk1 没有弹干净（没弹干净的原因见注释中对 popall 操作的说明），且 $stk1_{top}<a_i$，即，将要出现升序时，进行 popall 操作，清理掉比 $a_i$ 小的所有元素。特例：见 popall 操作的说明。

2. 对于 $col=1$ 的元素，即要入 stk2 的元素，不要有顾虑，进行 popall 操作再进栈即可。原理是先弹 stk1 比先入 stk2 更优。

• 注： popall 指的是弹出所有可以弹的元素，其中遵循先弹 stk1，尽可能不弹 stk2 的规则。我们维护一个 $now$ 来指出当前需弹的元素（序列是一个 $[1,n]$ 的排列）。若当入要向 stk1 中压入 $a_i$ 时，扫到 $stk2_{top} = now= a_i-1$，则可以等待入栈后再进行弹栈，直接退出即可。

Code

附几组关于 Part2 常见错误的数据。

#include<cstdio>
#include<vector>
#include<cstring>
#include<stack>
#include<algorithm>
using namespace std;
const int N=1050;
int n;
int a[N],f[N],col[N];
vector<int> e[N];
stack<int> stk1,stk2;
bool dfs(int u,int c){
    col[u]=c;
    for(int i:e[u]){
        if(col[i]==c)   return false;
        if(col[i]==-1 && !dfs(i,!c))    return false;
    }
    return true;
}
int now=1;
void popall(int lim){
    while(true){
        if(stk1.size()&&stk1.top()==now){
            stk1.pop();
            printf("b ");
            now++;
        }else if(stk2.size()&&stk2.top()==now){
            if(now==lim-1)
                break ;
            stk2.pop();
            printf("d ");
            now++;
        }else{
            // if(stk2.size())
            //     printf("\nstk=%d\n",stk2.top());
            break ;
        }
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    f[n+1]=n+1;
    for(int i=n;i>=1;i--)
        f[i]=min(f[i+1],a[i]);
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            if(a[i]<a[j]&&f[j+1]<a[i])
                e[i].push_back(j),e[j].push_back(i);
    memset(col,-1,sizeof(col));
    for(int i=1;i<=n;i++){
        if(col[i]==-1&&!dfs(i,0)){
            printf("0");
            return 0;
        }
    }
    for(int i=1;i<=n;i++){
        if(col[i]==0){
            // 字典序问题：第一个必须出 第二个栈可以等。
            int flag=0;
            // printf("\ni=%d now=%d\n", i,now);
            while(stk1.size()&&stk1.top()==now){
                stk1.pop();
                printf("b ");
                now++,flag=1;
            }
            // printf("\ni=%d now=%d flag=%d\n",i,now,flag);
            if(stk1.size()&&stk1.top()<a[i])
                popall(a[i]);
            stk1.push(a[i]);
            printf("a ");
        }else{
            popall(0);
            stk2.push(a[i]);
            // printf("\nnew_ele=%d\n",stk2.top());
            printf("c ");
        }
    }
    popall(0);
    return 0;
}

/*
test1:
6
2 3 1 4 5 6
output: a c a b b a d b a b a b
BUG:    a c a b b a a a d

test2:
8
1 3 4 2 7 5 8 6
output: a b a c a b b a a d b c a b b d
BUG:    a b a c a b b a d a b c a b b d

test3:
10
10 7 8 6 3 5 4 2 1 9
ANS:    a a c a a c c a a b b b d d b b a d b b
BUG:    a a c a a c c a a b b b a d d
*/

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std;

const int MaxN=1010,MaxM=MaxN*MaxN;
int Color[MaxN],Last[MaxN],Next[MaxM],To[MaxM],cnt;
inline void Insert(int from,int to){
	To[cnt]=to;
	Next[cnt]=Last[from];Last[from]=cnt++;
}
inline bool Dfs(int from,int color){
	Color[from]=color;
	for(int k=Last[from];k!=-1;k=Next[k]){
		if(!Color[To[k]]&&!Dfs(To[k],3-color))return False;
		if(Color[To[k]]==color)return False;
	}
	return True;
}
stack<int>S1,S2;
int Mini[MaxN],Arr[MaxN],n;
inline bool Free(int now){//记录操作
	if(!S1.empty()&&S1.top()==now)return S1.pop(),printf("b "),True;
	if(!S2.empty()&&S2.top()==now)return S2.pop(),printf("d "),True;
	return False;
}
int main(){
	int Task;scanf("%d",&Task);
	while(Task--){
		cnt=0;memset(Last,-1,sizeof(Last));
		memset(Color,0,sizeof(Color));
		scanf("%d",&n);
		for(int i=1;i<=n;i++)scanf("%d",&Arr[i]);
		//我们得到后缀最小值，判断什么数不能放在同一个栈
		Mini[n+1]=n+1;
		for(int i=n;i>=1;i--)
			Mini[i]=min(Mini[i+1],Arr[i]);
		for(int i=1;i<=n;i++)
			for(int j=i+1;j<=n;j++)
				if(Arr[i]<Arr[j]&&Mini[j+1]<Arr[i])
					Insert(i,j),Insert(j,i);
		bool flag=True;
		for(int i=1;i<=n;i++)
			if(!Color[i]&&!Dfs(i,1))
				{flag=False;puts("0");break;}
		//如果不能放在同一个栈的东西出奇环，必须放在一起，那就无解
		if(!flag)continue;
		int now=1;
		for(int i=1;i<=n;i++){
			if(Color[i]==1){//一定要放在S1
				while(!S1.empty()&&S1.top()<Arr[i])Free(now),now++;//放不进去就先释放
				S1.push(Arr[i]);printf("a ");
			}		
			else{//一定要放在S2
				while(true){
					while(!S1.empty()&&S1.top()==now)Free(now),now++;//字典序操作b优先
					while(!S2.empty()&&S2.top()<Arr[i])Free(now),now++;//放不进去的操作
					if(S2.empty()||S2.top()>Arr[i])break;
				}
				while(!S1.empty()&&S1.top()==now)Free(now),now++;//字典序操作b优先
				S2.push(Arr[i]);printf("c ");
			}
		}
		while(Free(now))now++;
		puts("");
	}
	return 0;
}