题目描述 Description
Tom最近在研究一个有趣的排序问题。如图所示，通过2个栈S1和S2，Tom希望借助以下4种操作实现将输入序列升序排序。
操作a
如果输入序列不为空，将第一个元素压入栈S1
操作b
如果栈S1不为空，将S1栈顶元素弹出至输出序列
操作c
如果输入序列不为空，将第一个元素压入栈S2
操作d
如果栈S2不为空，将S2栈顶元素弹出至输出序列
如果一个1~n的排列P可以通过一系列操作使得输出序列为1，2，…，(n-1)，n，Tom就称P是一个“可双栈排序排列”。例如(1,3,2,4)就是一个“可双栈排序序列”，而(2,3,4,1)不是。下图描述了一个将(1,3,2,4)排序的操作序列：<a,c,c,b,a,d,d,b>
当然，这样的操作序列有可能有几个，对于上例(1,3,2,4)，<a,c,c,b,a,d,d,b>是另外一个可行的操作序列。Tom希望知道其中字典序最小的操作序列是什么。
输入描述 Input Description
输入的第一行是一个整数n。
第二行有n个用空格隔开的正整数，构成一个1~n的排列。
输出描述 Output Description
输出共一行，如果输入的排列不是“可双栈排序排列”，输出数字0；否则输出字典序最小的操作序列，每两个操作之间用空格隔开，行尾没有空格。
样例输入 Sample Input
【样例1】
4
1 3 2 4
【样例2】
4
2 3 4 1
【样例3】
3
2 3 1
样例输出 Sample Output
【样例1】
a b a a b b a b
【样例2】
0
【样例3】
a c a b b d
数据范围及提示 Data Size & Hint
30%的数据满足： n<=10
50%的数据满足： n<=50
100%的数据满足： n<=1000
/*
不得不说，真的是很神奇的一道题
自己想着是要用字典序的，所以应该按顺序考虑a,b,c,d，然而noipT4怎么可能这么简单没有考虑一种最重要的情况，当i<j<k,且ak<ai<aj时，i和j必定不能在一个栈中，这就是解题的关键，利用染色的原理，处理出哪些元素在s1中，哪些元素在s2中，然后模拟出答案。
RE了N多次，rmq还是不太熟啊！
*/
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#define N 1010
using namespace std;
int a[N],head[N],mn[N][],color[N],s1[N],s2[N],n,top1,top2,cnt;
bool flag;
struct node
{
int v,pre;
};node e[N*N];
void rmq()
{
memset(mn,/,sizeof(mn));
for(int i=;i<=n;i++)mn[i][]=a[i];
for(int j=;j<=;j++)
for(int i=;i+(<<j)-<=n;i++)
mn[i][j]=min(mn[i][j-],mn[i+(<<j-)][j-]);
}
int query(int x,int y)
{
int k=log(y-x+)/log();
return min(mn[x][k],mn[y-(<<k)+][k]);
}
void add(int x,int y)
{
++cnt;
e[cnt].v=y;
e[cnt].pre=head[x];
head[x]=cnt;
}
void dfs(int x)
{
if(flag)return;
for(int i=head[x];i;i=e[i].pre)
if(!color[e[i].v])
{
color[e[i].v]=-color[x];
dfs(e[i].v);
}
else if(color[e[i].v]==color[x])
{
flag=true;return;
}
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
rmq();
for(int i=;i<=n;i++)
for(int j=i+;j<n;j++)//交了N多变都是RE，原因就是多写了个“=”，然后就用了log（0）
{
if(a[i]>a[j])continue;
int x=query(j+,n);
if(x<a[i])add(a[i],a[j]),add(a[j],a[i]);
}
for(int i=;i<=n;i++)
if(!color[i])
{
color[i]=;
dfs(i);
if(flag)
{
printf("");
return ;
}
}
int now=;
for(int i=;i<=n;i++)
{
if(color[a[i]]==)
{
if(a[i]==now){printf("a b ");now++;}
else
{
while(a[i]>s1[top1]&&top1)top1--,printf("b ");
s1[++top1]=a[i];printf("a ");
}
}
else
{
if(a[i]==now){printf("c d ");now++;}
else
{
while(a[i]>s2[top2]&&top2)top2--,printf("d ");
while(s1[top1]==now)top1--,printf("b "),now++;
s2[++top2]=a[i];printf("c ");
}
}
}
for(int i=now;i<=n;i++)
{
while(top1&&i==s1[top1])top1--,printf("b ");
while(top2&&i==s2[top2])top2--,printf("d ");
}
return ;
}